




"""simple docstring"""




a_            =   float('inf')

class        UpperCAmelCase_  :
		def __init__(		self							,		UpperCamelCase_   )		->   Union[str, Any]:
					__lowercase	:       Union[str, Any]				=   [0] * n
					__lowercase	:       Tuple				=   [0] * n
					__lowercase	:       Tuple				=   [0] * n
					__lowercase	:       Any				=   [[] for _ in range(UpperCamelCase__   )]
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_=0   )		->   Any:
					self.adj[a].append([b, len(self.adj[b]   ), c, 0]   )
					self.adj[b].append([a, len(self.adj[a]   ) - 1, rcap, 0]   )
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_   )		->   Union[str, Any]:






					if vertex == sink or not flow:
								return flow

					for i in range(self.ptr[vertex]							,		len(self.adj[vertex]   )   ):
								__lowercase	:       str				=   self.adj[vertex][i]
								if self.lvl[e[0]] == self.lvl[vertex] + 1:
											__lowercase	:       List[str]				=   self.depth_first_search(e[0]							,		UpperCamelCase__							,		min(UpperCamelCase__							,		e[2] - e[3]   )   )
											if p:
														self.adj[vertex][i][3] += p
														self.adj[e[0]][e[1]][3] -= p
														return p
								__lowercase	:       List[str]				=   self.ptr[vertex] + 1
					return 0
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_							,		UpperCamelCase_   )		->   str:
					__lowercase	,__lowercase	:       List[Any]				=   0, source
					for l in range(31   ):  # noqa: E741  l = 30 maybe faster for random data
								while True:
											__lowercase	,__lowercase	:       str				=   [0] * len(self.q   ), [0] * len(self.q   )
											__lowercase	,__lowercase	,__lowercase	:       List[str]				=   0, 1, 1
											while qi < qe and not self.lvl[sink]:
														__lowercase	:       Any				=   self.q[qi]
														qi += 1
														for e in self.adj[v]:
																	if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
																				__lowercase	:       List[Any]				=   e[0]
																				qe += 1
																				__lowercase	:       Dict				=   self.lvl[v] + 1

											__lowercase	:       Optional[int]				=   self.depth_first_search(UpperCamelCase__							,		UpperCamelCase__							,		UpperCamelCase__   )
											while p:
														flow += p
														__lowercase	:       str				=   self.depth_first_search(UpperCamelCase__							,		UpperCamelCase__							,		UpperCamelCase__   )

											if not self.lvl[sink]:
														break

					return flow


a_            =   Dinic(1_0)
a_            =   0
a_            =   9
for vertex in range(1, 5):
			graph.add_edge(source, vertex, 1)
for vertex in range(5, 9):
			graph.add_edge(vertex, sink, 1)
for vertex in range(1, 5):
			graph.add_edge(vertex, vertex + 4, 1)

# Now we can know that is the maximum flow(source -> sink)
print(graph.max_flow(source, sink))









"""simple docstring"""




import json
import os
import shutil
import tempfile
import unittest

from transformers import is_speech_available, is_torch_available
from transformers.models.speechta import SpeechTaTokenizer
from transformers.testing_utils import get_tests_dir, require_torch
from transformers.utils import FEATURE_EXTRACTOR_NAME


if is_speech_available() and is_torch_available():
			from transformers import SpeechTaFeatureExtractor, SpeechTaProcessor

			from .test_feature_extraction_speechta import floats_list


a_            =   get_tests_dir('fixtures/test_sentencepiece_bpe_char.model')

@require_torch
class        UpperCAmelCase_  (	unittest.TestCase						):
		def 					_lowerCamelCase    (		self   )		->   Dict:
					__lowercase	:       Union[str, Any]				=   tempfile.mkdtemp()

					__lowercase	:       List[str]				=   SpeechTaTokenizer(UpperCamelCase_   )
					tokenizer.save_pretrained(self.tmpdirname   )

					__lowercase	:       Dict				=   {
					    '''feature_size''': 1,
					    '''padding_value''': 0.0,
					    '''sampling_rate''': 1_60_00,
					    '''do_normalize''': False,
					    '''num_mel_bins''': 80,
					    '''hop_length''': 16,
					    '''win_length''': 64,
					    '''win_function''': '''hann_window''',
					    '''fmin''': 80,
					    '''fmax''': 76_00,
					    '''mel_floor''': 1E-10,
					    '''reduction_factor''': 2,
					    '''return_attention_mask''': True,
					}

					__lowercase	:       List[Any]				=   os.path.join(self.tmpdirname							,		UpperCamelCase_   )
					with open(self.feature_extraction_file							,		'''w'''							,		encoding='''utf-8'''   ) as fp:
								fp.write(json.dumps(UpperCamelCase_   ) + '''\n'''   )
		def 					_lowerCamelCase    (		self							,		**UpperCamelCase_   )		->   Union[str, Any]:
					return SpeechTaTokenizer.from_pretrained(self.tmpdirname							,		**UpperCamelCase_   )
		def 					_lowerCamelCase    (		self							,		**UpperCamelCase_   )		->   Optional[Any]:
					return SpeechTaFeatureExtractor.from_pretrained(self.tmpdirname							,		**UpperCamelCase_   )
		def 					_lowerCamelCase    (		self   )		->   Any:
					shutil.rmtree(self.tmpdirname   )
		def 					_lowerCamelCase    (		self   )		->   Union[str, Any]:
					__lowercase	:       List[str]				=   self.get_tokenizer()
					__lowercase	:       int				=   self.get_feature_extractor()

					__lowercase	:       Any				=   SpeechTaProcessor(tokenizer=UpperCamelCase_							,		feature_extractor=UpperCamelCase_   )

					processor.save_pretrained(self.tmpdirname   )
					__lowercase	:       List[Any]				=   SpeechTaProcessor.from_pretrained(self.tmpdirname   )

					self.assertEqual(processor.tokenizer.get_vocab()							,		tokenizer.get_vocab()   )
					self.assertIsInstance(processor.tokenizer							,		UpperCamelCase_   )

					self.assertEqual(processor.feature_extractor.to_json_string()							,		feature_extractor.to_json_string()   )
					self.assertIsInstance(processor.feature_extractor							,		UpperCamelCase_   )
		def 					_lowerCamelCase    (		self   )		->   Optional[Any]:
					__lowercase	:       Optional[int]				=   SpeechTaProcessor(tokenizer=self.get_tokenizer()							,		feature_extractor=self.get_feature_extractor()   )
					processor.save_pretrained(self.tmpdirname   )

					__lowercase	:       str				=   self.get_tokenizer(bos_token='''(BOS)'''							,		eos_token='''(EOS)'''   )
					__lowercase	:       Dict				=   self.get_feature_extractor(do_normalize=UpperCamelCase_							,		padding_value=1.0   )

					__lowercase	:       Tuple				=   SpeechTaProcessor.from_pretrained(
					    self.tmpdirname							,		bos_token='''(BOS)'''							,		eos_token='''(EOS)'''							,		do_normalize=UpperCamelCase_							,		padding_value=1.0   )

					self.assertEqual(processor.tokenizer.get_vocab()							,		tokenizer_add_kwargs.get_vocab()   )
					self.assertIsInstance(processor.tokenizer							,		UpperCamelCase_   )

					self.assertEqual(processor.feature_extractor.to_json_string()							,		feature_extractor_add_kwargs.to_json_string()   )
					self.assertIsInstance(processor.feature_extractor							,		UpperCamelCase_   )
		def 					_lowerCamelCase    (		self   )		->   List[str]:
					__lowercase	:       Optional[Any]				=   self.get_feature_extractor()
					__lowercase	:       Optional[Any]				=   self.get_tokenizer()

					__lowercase	:       Union[str, Any]				=   SpeechTaProcessor(tokenizer=UpperCamelCase_							,		feature_extractor=UpperCamelCase_   )

					__lowercase	:       int				=   floats_list((3, 10_00)   )

					__lowercase	:       str				=   feature_extractor(audio=UpperCamelCase_							,		return_tensors='''np'''   )
					__lowercase	:       Dict				=   processor(audio=UpperCamelCase_							,		return_tensors='''np'''   )

					for key in input_feat_extract.keys():
								self.assertAlmostEqual(input_feat_extract[key].sum()							,		input_processor[key].sum()							,		delta=1E-2   )
		def 					_lowerCamelCase    (		self   )		->   List[Any]:
					__lowercase	:       str				=   self.get_feature_extractor()
					__lowercase	:       str				=   self.get_tokenizer()

					__lowercase	:       Union[str, Any]				=   SpeechTaProcessor(tokenizer=UpperCamelCase_							,		feature_extractor=UpperCamelCase_   )

					__lowercase	:       Optional[int]				=   floats_list((3, 10_00)   )

					__lowercase	:       List[str]				=   feature_extractor(audio_target=UpperCamelCase_							,		return_tensors='''np'''   )
					__lowercase	:       List[str]				=   processor(audio_target=UpperCamelCase_							,		return_tensors='''np'''   )

					for key in input_feat_extract.keys():
								self.assertAlmostEqual(input_feat_extract[key].sum()							,		input_processor[key].sum()							,		delta=1E-2   )
		def 					_lowerCamelCase    (		self   )		->   Any:
					__lowercase	:       List[Any]				=   self.get_feature_extractor()
					__lowercase	:       List[str]				=   self.get_tokenizer()

					__lowercase	:       Union[str, Any]				=   SpeechTaProcessor(tokenizer=UpperCamelCase_							,		feature_extractor=UpperCamelCase_   )

					__lowercase	:       List[str]				=   '''This is a test string'''

					__lowercase	:       Any				=   processor(text=UpperCamelCase_   )
					__lowercase	:       Optional[int]				=   tokenizer(UpperCamelCase_   )

					for key in encoded_tok.keys():
								self.assertListEqual(encoded_tok[key]							,		encoded_processor[key]   )
		def 					_lowerCamelCase    (		self   )		->   str:
					__lowercase	:       int				=   self.get_feature_extractor()
					__lowercase	:       List[str]				=   self.get_tokenizer()

					__lowercase	:       List[Any]				=   SpeechTaProcessor(tokenizer=UpperCamelCase_							,		feature_extractor=UpperCamelCase_   )

					__lowercase	:       Union[str, Any]				=   '''This is a test string'''

					__lowercase	:       Tuple				=   processor(text_target=UpperCamelCase_   )
					__lowercase	:       Optional[int]				=   tokenizer(UpperCamelCase_   )

					for key in encoded_tok.keys():
								self.assertListEqual(encoded_tok[key]							,		encoded_processor[key]   )
		def 					_lowerCamelCase    (		self   )		->   Optional[Any]:
					__lowercase	:       Optional[int]				=   self.get_feature_extractor()
					__lowercase	:       str				=   self.get_tokenizer()

					__lowercase	:       int				=   SpeechTaProcessor(tokenizer=UpperCamelCase_							,		feature_extractor=UpperCamelCase_   )

					__lowercase	:       Optional[Any]				=   [[1, 4, 5, 8, 1, 0, 8], [3, 4, 3, 1, 1, 8, 9]]

					__lowercase	:       str				=   processor.batch_decode(UpperCamelCase_   )
					__lowercase	:       int				=   tokenizer.batch_decode(UpperCamelCase_   )

					self.assertListEqual(UpperCamelCase_							,		UpperCamelCase_   )
		def 					_lowerCamelCase    (		self   )		->   Optional[int]:
					__lowercase	:       Union[str, Any]				=   self.get_feature_extractor()
					__lowercase	:       int				=   self.get_tokenizer()

					__lowercase	:       Optional[int]				=   SpeechTaProcessor(tokenizer=UpperCamelCase_							,		feature_extractor=UpperCamelCase_   )

					self.assertListEqual(
					    processor.model_input_names							,		feature_extractor.model_input_names							,		msg='''`processor` and `feature_extractor` model input names do not match'''							,		)



