



'''simple docstring'''



lowerCAmelCase						:		Union[str, Any]						      = float('''inf''')






class        UpperCAmelCase__						:



					def __init__(     self      ,					UpperCamelCase  )  ->      int:
						__lowerCAmelCase       				=	[0] * n
						__lowerCAmelCase       				=	[0] * n
						__lowerCAmelCase       				=	[0] * n
						__lowerCAmelCase       				=	[[] for _ in range(UpperCamelCase  )]



					def 							UpperCAmelCase_			(     self      ,					UpperCamelCase      ,					UpperCamelCase      ,					UpperCamelCase      ,					UpperCamelCase=0  )  ->      Optional[int]:
						self.adj[a].append([b, len(self.adj[b]  ), c, 0]  )
						self.adj[b].append([a, len(self.adj[a]  ) - 1, rcap, 0]  )



					def 							UpperCAmelCase_			(     self      ,					UpperCamelCase      ,					UpperCamelCase      ,					UpperCamelCase  )  ->      Tuple:
						if vertex == sink or not flow:
							return flow

						for i in range(self.ptr[vertex]      ,					len(self.adj[vertex]  )  ):
							__lowerCAmelCase       				=	self.adj[vertex][i]
							if self.lvl[e[0]] == self.lvl[vertex] + 1:
								__lowerCAmelCase       				=	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
							__lowerCAmelCase       				=	self.ptr[vertex] + 1
						return 0



					def 							UpperCAmelCase_			(     self      ,					UpperCamelCase      ,					UpperCamelCase  )  ->      Optional[Any]:
						__lowerCAmelCase				,							__lowerCAmelCase       				=	0, source
						for l in range(31  ):  # noqa: E741  l = 30 maybe faster for random data
							while True:
								__lowerCAmelCase				,							__lowerCAmelCase       				=	[0] * len(self.q  ), [0] * len(self.q  )
								__lowerCAmelCase				,							__lowerCAmelCase				,							__lowerCAmelCase       				=	0, 1, 1
								while qi < qe and not self.lvl[sink]:
									__lowerCAmelCase       				=	self.q[qi]
									qi += 1
									for e in self.adj[v]:
										if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
											__lowerCAmelCase       				=	e[0]
											qe += 1
											__lowerCAmelCase       				=	self.lvl[v] + 1

								__lowerCAmelCase       				=	self.depth_first_search(UpperCamelCase      ,					UpperCamelCase      ,					UpperCamelCase  )
								while p:
									flow += p
									__lowerCAmelCase       				=	self.depth_first_search(UpperCamelCase      ,					UpperCamelCase      ,					UpperCamelCase  )

								if not self.lvl[sink]:
									break

						return flow
lowerCAmelCase						:		Any						      = Dinic(1_0)
lowerCAmelCase						:		str						      = 0
lowerCAmelCase						:		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						:		Tuple						      = '''
# Diffusers installation
! pip install diffusers transformers datasets accelerate
# 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/diffusers.git
'''

lowerCAmelCase						:		Tuple						      = [{'''type''': '''code''', '''content''': INSTALL_CONTENT}]