



'''simple docstring'''




UpperCamelCase__	:     int    =			float('''inf''')






class 						_UpperCamelCase  :


			'''simple docstring'''

			def __init__(							self					:			List[str]							,					lowerCAmelCase__					:			int						):





					"""simple docstring"""






					__SCREAMING_SNAKE_CASE	:		Tuple   	=		[0] * n
					__SCREAMING_SNAKE_CASE	:		Optional[Any]   	=		[0] * n
					__SCREAMING_SNAKE_CASE	:		List[Any]   	=		[0] * n
					__SCREAMING_SNAKE_CASE	:		Union[str, Any]   	=		[[] for _ in range(lowerCAmelCase__						)]

			def UpperCamelCase__ (							self					:			str							,					lowerCAmelCase__					:			Optional[int]							,					lowerCAmelCase__					:			Union[str, Any]							,					lowerCAmelCase__					:			Optional[int]							,					lowerCAmelCase__					:			str=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 UpperCamelCase__ (							self					:			str							,					lowerCAmelCase__					:			Optional[int]							,					lowerCAmelCase__					:			List[str]							,					lowerCAmelCase__					:			Dict						):





					"""simple docstring"""






					if vertex == sink or not flow:
							return flow

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



			def UpperCamelCase__ (							self					:			Dict							,					lowerCAmelCase__					:			str							,					lowerCAmelCase__					:			Union[str, Any]						):





					"""simple docstring"""






					__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	:		Any   	=		0, source
					for l in range(3_1						):  # noqa: E741  l = 30 maybe faster for random data
							while True:
									__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	:		Any   	=		[0] * len(self.q						), [0] * len(self.q						)
									__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	,						__SCREAMING_SNAKE_CASE	:		List[str]   	=		0, 1, 1
									while qi < qe and not self.lvl[sink]:
											__SCREAMING_SNAKE_CASE	:		Dict   	=		self.q[qi]
											qi += 1
											for e in self.adj[v]:
													if not self.lvl[e[0]] and (e[2] - e[3]) >> (3_0 - l):
															__SCREAMING_SNAKE_CASE	:		int   	=		e[0]
															qe += 1
															__SCREAMING_SNAKE_CASE	:		Tuple   	=		self.lvl[v] + 1

									__SCREAMING_SNAKE_CASE	:		int   	=		self.depth_first_search(lowerCAmelCase__							,					lowerCAmelCase__							,					lowerCAmelCase__						)
									while p:
											flow += p
											__SCREAMING_SNAKE_CASE	:		Dict   	=		self.depth_first_search(lowerCAmelCase__							,					lowerCAmelCase__							,					lowerCAmelCase__						)

									if not self.lvl[sink]:
											break

					return flow
UpperCamelCase__	:     Tuple    =			Dinic(10)
UpperCamelCase__	:     str    =			0
UpperCamelCase__	:     int    =			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'''




from __future__ import annotations


def     lowerCAmelCase_       (     _lowerCamelCase:       list[int | float] ):
		if len(_lowerCamelCase ) == 0:
				raise ValueError("""find_min() arg is an empty sequence""" )
		__SCREAMING_SNAKE_CASE	:		List[str]   	=		nums[0]
		for num in nums:
				__SCREAMING_SNAKE_CASE	:		int   	=		min(_lowerCamelCase	,				_lowerCamelCase )
		return min_num


if __name__ == "__main__":
						import doctest

						doctest.testmod(verbose=True)