




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

class 	__lowerCAmelCase			:
							def __init__(		self		:Dict	,   __magic_name__		:Optional[int]       ):







								'''simple docstring'''







								a		       =							[0] * n
								a		       =							[0] * n
								a		       =							[0] * n
								a		       =							[[] for _ in range(__magic_name__       )]
							def    lowerCamelCase__							(		self		:Tuple	,   __magic_name__		:List[str]	,   __magic_name__		:Union[str, Any]	,   __magic_name__		:Optional[Any]	,   __magic_name__		: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    lowerCamelCase__							(		self		:str	,   __magic_name__		:List[Any]	,   __magic_name__		:List[Any]	,   __magic_name__		:Union[str, Any]       ):







								'''simple docstring'''







								if vertex == sink or not flow:
									return flow

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





							def    lowerCamelCase__							(		self		:Dict	,   __magic_name__		:List[Any]	,   __magic_name__		:Any       ):







								'''simple docstring'''







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

										a		       =							self.depth_first_search(__magic_name__	,   __magic_name__	,   __magic_name__       )
										while p:
											flow += p
											a		       =							self.depth_first_search(__magic_name__	,   __magic_name__	,   __magic_name__       )

										if not self.lvl[sink]:
											break

								return flow
__UpperCamelCase      : str					      =   Dinic(10)
__UpperCamelCase      : Optional[Any]					      =   0
__UpperCamelCase      : 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))







from itertools import combinations, product





def 	__A	(			__lowerCamelCase							,    __lowerCamelCase							,    __lowerCamelCase							,    __lowerCamelCase					)   -> bool:
	if xa == ya == 0 or xa == ya == 0:
		return False
	a		       =							xa * xa + ya * ya
	a		       =							xa * xa + ya * ya
	a		       =							(xa - xa) * (xa - xa) + (ya - ya) * (ya - ya)
	return (
	    a_square + b_square == c_square
	    or a_square + c_square == b_square
	    or b_square + c_square == a_square
	)





def 	__A	(			__lowerCamelCase = 50					)   -> int:
	return sum(
	    1
	    for pta, pta in combinations(product(range(limit + 1					)							,    repeat=2					)							,    2					)
	    if is_right(*__lowerCamelCase							,    *__lowerCamelCase					)					)


if __name__ == "__main__":
		print(F'{solution() = }')

