



'''simple docstring'''







SCREAMING_SNAKE_CASE__     : Union[str, Any]				=   float("""inf""")




class 				__lowerCAmelCase:






			def __init__(   self  :							int      ,       SCREAMING_SNAKE_CASE  :							List[Any]	):




					"""simple docstring"""







					SCREAMING_SNAKE_CASE_						:Optional[Any]										=      [0] * n
					SCREAMING_SNAKE_CASE_						:List[str]										=      [0] * n
					SCREAMING_SNAKE_CASE_						:Any										=      [0] * n
					SCREAMING_SNAKE_CASE_						:Union[str, Any]										=      [[] for _ in range(SCREAMING_SNAKE_CASE	)]






			def 				_lowercase	(   self  :							List[Any]      ,       SCREAMING_SNAKE_CASE  :							List[str]      ,       SCREAMING_SNAKE_CASE  :							int      ,       SCREAMING_SNAKE_CASE  :							Union[str, Any]      ,       SCREAMING_SNAKE_CASE  :							Optional[int]=0	):




					"""simple docstring"""







					self.adj[a].append([b, len(self.adj[b]	), c, 0]	)
					self.adj[b].append([a, len(self.adj[a]	) - 1, rcap, 0]	)






			def 				_lowercase	(   self  :							Optional[Any]      ,       SCREAMING_SNAKE_CASE  :							Optional[int]      ,       SCREAMING_SNAKE_CASE  :							Optional[Any]      ,       SCREAMING_SNAKE_CASE  :							int	):




					"""simple docstring"""







					if vertex == sink or not flow:
							return flow

					for i in range(self.ptr[vertex]      ,       len(self.adj[vertex]	)	):
							SCREAMING_SNAKE_CASE_						:Dict										=      self.adj[vertex][i]
							if self.lvl[e[0]] == self.lvl[vertex] + 1:
									SCREAMING_SNAKE_CASE_						:Dict										=      self.depth_first_search(e[0]      ,       SCREAMING_SNAKE_CASE      ,       min(SCREAMING_SNAKE_CASE      ,       e[2] - e[3]	)	)
									if p:
											self.adj[vertex][i][3] += p
											self.adj[e[0]][e[1]][3] -= p
											return p
							SCREAMING_SNAKE_CASE_						:List[str]										=      self.ptr[vertex] + 1
					return 0






			def 				_lowercase	(   self  :							Dict      ,       SCREAMING_SNAKE_CASE  :							Dict      ,       SCREAMING_SNAKE_CASE  :							Optional[int]	):




					"""simple docstring"""







					SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:List[str]										=      0, source
					for l in range(31	):  # noqa: E741  l = 30 maybe faster for random data
							while True:
									SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:str										=      [0] * len(self.q	), [0] * len(self.q	)
									SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:Dict										=      0, 1, 1
									while qi < qe and not self.lvl[sink]:
											SCREAMING_SNAKE_CASE_						:List[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):
															SCREAMING_SNAKE_CASE_						:List[str]										=      e[0]
															qe += 1
															SCREAMING_SNAKE_CASE_						:Dict										=      self.lvl[v] + 1

									SCREAMING_SNAKE_CASE_						:int										=      self.depth_first_search(SCREAMING_SNAKE_CASE      ,       SCREAMING_SNAKE_CASE      ,       SCREAMING_SNAKE_CASE	)
									while p:
											flow += p
											SCREAMING_SNAKE_CASE_						:str										=      self.depth_first_search(SCREAMING_SNAKE_CASE      ,       SCREAMING_SNAKE_CASE      ,       SCREAMING_SNAKE_CASE	)

									if not self.lvl[sink]:
											break

					return flow


SCREAMING_SNAKE_CASE__     : Any				=   Dinic(10)
SCREAMING_SNAKE_CASE__     : str				=   0
SCREAMING_SNAKE_CASE__     : Union[str, Any]				=   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'''



lowerCAmelCase						:		Any						      = '''
# Transformers installation
! pip install transformers datasets
# To install from source instead of the last release, comment the command above and uncomment the following one.
# ! pip install git+https://github.com/huggingface/transformers.git
'''

lowerCAmelCase						:		Any						      = [{'''type''': '''code''', '''content''': INSTALL_CONTENT}]
lowerCAmelCase						:		str						      = {
    '''{processor_class}''': '''FakeProcessorClass''',
    '''{model_class}''': '''FakeModelClass''',
    '''{object_class}''': '''FakeObjectClass''',
}