


'''simple docstring'''






from __future__ import annotations

import math
import random
from collections.abc import Collection
from typing import overload
class 						__UpperCamelCase	:





							def __init__(  self		:Optional[Any]  ,_UpperCamelCase		:Dict = None			):
									if components is None:
											snake_case_		:							Optional[int]			       =						[]
									snake_case_		:							Dict			       =						list(UpperCamelCase__			)





							def __len__(  self		:int			):
									return len(self.__components			)





							def __str__(  self		:Optional[Any]			):
									return "(" + ",".join(map(UpperCamelCase__  ,self.__components			)			) + ")"





							def __add__(  self		:Any  ,_UpperCamelCase		:List[Any]			):
									snake_case_		:							Optional[int]			       =						len(self			)
									if size == len(UpperCamelCase__			):
											snake_case_		:							Optional[int]			       =						[self.__components[i] + other.component(UpperCamelCase__			) for i in range(UpperCamelCase__			)]
											return Vector(UpperCamelCase__			)
									else:
											raise Exception("""must have the same size"""			)





							def __sub__(  self		:Optional[int]  ,_UpperCamelCase		:List[str]			):
									snake_case_		:							Optional[Any]			       =						len(self			)
									if size == len(UpperCamelCase__			):
											snake_case_		:							List[Any]			       =						[self.__components[i] - other.component(UpperCamelCase__			) for i in range(UpperCamelCase__			)]
											return Vector(UpperCamelCase__			)
									else:  # error case
											raise Exception("""must have the same size"""			)





							@overload
							def __mul__(  self		:str  ,_UpperCamelCase		:Union[str, Any]			):
									...





							@overload
							def __mul__(  self		:Tuple  ,_UpperCamelCase		:Optional[Any]			):
									...





							def __mul__(  self		:int  ,_UpperCamelCase		:Dict			):
									if isinstance(UpperCamelCase__  ,(float, int)			):
											snake_case_		:							Optional[Any]			       =						[c * other for c in self.__components]
											return Vector(UpperCamelCase__			)
									elif isinstance(UpperCamelCase__  ,UpperCamelCase__			) and len(self			) == len(UpperCamelCase__			):
											snake_case_		:							Optional[int]			       =						len(self			)
											snake_case_		:							List[Any]			       =						[self.__components[i] * other.component(UpperCamelCase__			) for i in range(UpperCamelCase__			)]
											return sum(UpperCamelCase__			)
									else:  # error case
											raise Exception("""invalid operand!"""			)





							def 		a__   (  self		:int			):
									return Vector(self.__components			)





							def 		a__   (  self		:Dict  ,_UpperCamelCase		:Tuple			):
									if isinstance(UpperCamelCase__  ,UpperCamelCase__			) and -len(self.__components			) <= i < len(self.__components			):
											return self.__components[i]
									else:
											raise Exception("""index out of range"""			)





							def 		a__   (  self		:Optional[int]  ,_UpperCamelCase		:Dict  ,_UpperCamelCase		:List[Any]			):
									assert -len(self.__components			) <= pos < len(self.__components			)
									snake_case_		:							Tuple			       =						value





							def 		a__   (  self		:Optional[int]			):
									if len(self.__components			) == 0:
											raise Exception("""Vector is empty"""			)
									snake_case_		:							Tuple			       =						[c**2 for c in self.__components]
									return math.sqrt(sum(UpperCamelCase__			)			)





							def 		a__   (  self		:int  ,_UpperCamelCase		:Tuple  ,_UpperCamelCase		:List[Any] = False			):
									snake_case_		:							Dict			       =						self * other
									snake_case_		:							Any			       =						self.euclidean_length() * other.euclidean_length()
									if deg:
											return math.degrees(math.acos(num / den			)			)
									else:
											return math.acos(num / den			)





def      UpperCAmelCase      (		lowerCamelCase_  :int ):







		'''simple docstring'''
		assert isinstance(__UpperCamelCase				,      __UpperCamelCase )
		return Vector([0] * dimension )





def      UpperCAmelCase      (		lowerCamelCase_  :int				,      lowerCamelCase_  :int ):







		'''simple docstring'''
		assert isinstance(__UpperCamelCase				,      __UpperCamelCase ) and (isinstance(__UpperCamelCase				,      __UpperCamelCase ))
		snake_case_		:							Union[str, Any]			       =						[0] * dimension
		snake_case_		:							str			       =						1
		return Vector(__UpperCamelCase )





def      UpperCAmelCase      (		lowerCamelCase_  :float				,      lowerCamelCase_  :Vector				,      lowerCamelCase_  :Vector ):







		'''simple docstring'''
		assert (
		    isinstance(__UpperCamelCase				,      __UpperCamelCase )
		    and isinstance(__UpperCamelCase				,      __UpperCamelCase )
		    and (isinstance(__UpperCamelCase				,      (int, float) ))
		)
		return x * scalar + y





def      UpperCAmelCase      (		lowerCamelCase_  :int				,      lowerCamelCase_  :int				,      lowerCamelCase_  :int ):







		'''simple docstring'''
		random.seed(__UpperCamelCase )
		snake_case_		:							Optional[Any]			       =						[random.randint(__UpperCamelCase				,      __UpperCamelCase ) for _ in range(__UpperCamelCase )]
		return Vector(__UpperCamelCase )
class 						__UpperCamelCase	:





							def __init__(  self		:List[Any]  ,_UpperCamelCase		:List[str]  ,_UpperCamelCase		:List[Any]  ,_UpperCamelCase		:int			):
									snake_case_		:							Optional[Any]			       =						matrix
									snake_case_		:							Optional[int]			       =						w
									snake_case_		:							Any			       =						h





							def __str__(  self		:str			):
									snake_case_		:							Optional[int]			       =						''''''
									for i in range(self.__height			):
											ans += "|"
											for j in range(self.__width			):
													if j < self.__width - 1:
															ans += str(self.__matrix[i][j]			) + ","
													else:
															ans += str(self.__matrix[i][j]			) + "|\n"
									return ans





							def __add__(  self		:Dict  ,_UpperCamelCase		:str			):
									if self.__width == other.width() and self.__height == other.height():
											snake_case_		:							Dict			       =						[]
											for i in range(self.__height			):
													snake_case_		:							Any			       =						[
													    self.__matrix[i][j] + other.component(UpperCamelCase__  ,UpperCamelCase__			)
													    for j in range(self.__width			)
													]
													matrix.append(UpperCamelCase__			)
											return Matrix(UpperCamelCase__  ,self.__width  ,self.__height			)
									else:
											raise Exception("""matrix must have the same dimension!"""			)





							def __sub__(  self		:Optional[int]  ,_UpperCamelCase		:Union[str, Any]			):
									if self.__width == other.width() and self.__height == other.height():
											snake_case_		:							List[str]			       =						[]
											for i in range(self.__height			):
													snake_case_		:							int			       =						[
													    self.__matrix[i][j] - other.component(UpperCamelCase__  ,UpperCamelCase__			)
													    for j in range(self.__width			)
													]
													matrix.append(UpperCamelCase__			)
											return Matrix(UpperCamelCase__  ,self.__width  ,self.__height			)
									else:
											raise Exception("""matrices must have the same dimension!"""			)





							@overload
							def __mul__(  self		:int  ,_UpperCamelCase		:Optional[Any]			):
									...





							@overload
							def __mul__(  self		:Any  ,_UpperCamelCase		:Any			):
									...





							def __mul__(  self		:Optional[Any]  ,_UpperCamelCase		:int			):
									if isinstance(UpperCamelCase__  ,UpperCamelCase__			):  # matrix-vector
											if len(UpperCamelCase__			) == self.__width:
													snake_case_		:							Optional[Any]			       =						zero_vector(self.__height			)
													for i in range(self.__height			):
															snake_case_		:							Optional[Any]			       =						[
															    self.__matrix[i][j] * other.component(UpperCamelCase__			)
															    for j in range(self.__width			)
															]
															ans.change_component(UpperCamelCase__  ,sum(UpperCamelCase__			)			)
													return ans
											else:
													raise Exception(
													    """vector must have the same size as the """
													    """number of columns of the matrix!"""			)
									elif isinstance(UpperCamelCase__  ,(int, float)			):  # matrix-scalar
											snake_case_		:							List[str]			       =						[
											    [self.__matrix[i][j] * other for j in range(self.__width			)]
											    for i in range(self.__height			)
											]
											return Matrix(UpperCamelCase__  ,self.__width  ,self.__height			)
									return None





							def 		a__   (  self		:List[str]			):
									return self.__height





							def 		a__   (  self		:Optional[int]			):
									return self.__width





							def 		a__   (  self		:Optional[int]  ,_UpperCamelCase		:Optional[int]  ,_UpperCamelCase		:Tuple			):
									if 0 <= x < self.__height and 0 <= y < self.__width:
											return self.__matrix[x][y]
									else:
											raise Exception("""change_component: indices out of bounds"""			)





							def 		a__   (  self		:List[str]  ,_UpperCamelCase		:Dict  ,_UpperCamelCase		:Union[str, Any]  ,_UpperCamelCase		:Any			):
									if 0 <= x < self.__height and 0 <= y < self.__width:
											snake_case_		:							Any			       =						value
									else:
											raise Exception("""change_component: indices out of bounds"""			)





							def 		a__   (  self		:Dict  ,_UpperCamelCase		:Union[str, Any]  ,_UpperCamelCase		:int			):
									if self.__height != self.__width:
											raise Exception("""Matrix is not square"""			)
									snake_case_		:							int			       =						self.__matrix[:x] + self.__matrix[x + 1 :]
									for i in range(len(UpperCamelCase__			)			):
											snake_case_		:							Any			       =						minor[i][:y] + minor[i][y + 1 :]
									return Matrix(UpperCamelCase__  ,self.__width - 1  ,self.__height - 1			).determinant()





							def 		a__   (  self		:str  ,_UpperCamelCase		:List[str]  ,_UpperCamelCase		:Union[str, Any]			):
									if self.__height != self.__width:
											raise Exception("""Matrix is not square"""			)
									if 0 <= x < self.__height and 0 <= y < self.__width:
											return (-1) ** (x + y) * self.minor(UpperCamelCase__  ,UpperCamelCase__			)
									else:
											raise Exception("""Indices out of bounds"""			)





							def 		a__   (  self		:Optional[Any]			):
									if self.__height != self.__width:
											raise Exception("""Matrix is not square"""			)
									if self.__height < 1:
											raise Exception("""Matrix has no element"""			)
									elif self.__height == 1:
											return self.__matrix[0][0]
									elif self.__height == 2:
											return (
											    self.__matrix[0][0] * self.__matrix[1][1]
											    - self.__matrix[0][1] * self.__matrix[1][0]
											)
									else:
											snake_case_		:							Dict			       =						[
											    self.__matrix[0][y] * self.cofactor(0  ,UpperCamelCase__			) for y in range(self.__width			)
											]
											return sum(UpperCamelCase__			)





def      UpperCAmelCase      (		lowerCamelCase_  :int ):







		'''simple docstring'''
		snake_case_		:							list[list[float]]			       =						[[0] * n for _ in range(__UpperCamelCase )]
		return Matrix(__UpperCamelCase				,      __UpperCamelCase				,      __UpperCamelCase )






def      UpperCAmelCase      (		lowerCamelCase_  :int				,      lowerCamelCase_  :int				,      lowerCamelCase_  :int				,      lowerCamelCase_  :int ):







		'''simple docstring'''
		random.seed(__UpperCamelCase )
		snake_case_		:							list[list[float]]			       =						[
		    [random.randint(__UpperCamelCase				,      __UpperCamelCase ) for _ in range(__UpperCamelCase )] for _ in range(__UpperCamelCase )
		]
		return Matrix(__UpperCamelCase				,      __UpperCamelCase				,      __UpperCamelCase )



'''simple docstring'''






def      UpperCAmelCase      (		lowerCamelCase_  :Tuple				,      lowerCamelCase_  :Optional[Any]				,      lowerCamelCase_  :str				,      lowerCamelCase_  :str ):







		'''simple docstring'''
		# Return True if there is node that has not iterated.
		snake_case_		:							Optional[int]			       =						[False] * len(lowerCamelCase_ )
		snake_case_		:							Dict			       =						[]
		queue.append(lowerCamelCase_ )
		snake_case_		:							Tuple			       =						True

		while queue:
				snake_case_		:							Union[str, Any]			       =						queue.pop(0 )
				for ind in range(len(graph[u] ) ):
						if visited[ind] is False and graph[u][ind] > 0:
								queue.append(lowerCamelCase_ )
								snake_case_		:							str			       =						True
								snake_case_		:							Optional[Any]			       =						u

		return visited[t]





def      UpperCAmelCase      (		lowerCamelCase_  :Optional[Any]				,      lowerCamelCase_  :Dict				,      lowerCamelCase_  :Union[str, Any] ):







		'''simple docstring'''
		# This array is filled by BFS and to store path
		snake_case_		:							Optional[int]			       =						[-1] * (len(lowerCamelCase_ ))
		snake_case_		:							Tuple			       =						0
		while bfs(lowerCamelCase_				,      lowerCamelCase_				,      lowerCamelCase_				,      lowerCamelCase_ ):
				snake_case_		:							int			       =						float("""Inf""" )
				snake_case_		:							Any			       =						sink

				while s != source:
						# Find the minimum value in select path
						snake_case_		:							Optional[Any]			       =						min(lowerCamelCase_				,      graph[parent[s]][s] )
						snake_case_		:							Union[str, Any]			       =						parent[s]

				max_flow += path_flow
				snake_case_		:							Dict			       =						sink

				while v != source:
						snake_case_		:							Optional[int]			       =						parent[v]
						graph[u][v] -= path_flow
						graph[v][u] += path_flow
						snake_case_		:							Any			       =						parent[v]
		return max_flow


__A	:	Union[str, Any]     =     [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0],
]

__A,   __A	:	Union[str, Any]     =     0, 5






print(ford_fulkerson(graph, source, sink))