




class 		UpperCamelCase__	:

    '''simple docstring'''



    def __init__(    self     ,  UpperCamelCase__     ,  UpperCamelCase__     ,  UpperCamelCase__     )     ->      Optional[Any]:
           lowerCamelCase   :      Optional[int]			 =					None
           lowerCamelCase   :      List[Any]			 =					None
           lowerCamelCase   :      Tuple			 =					graph

           self._normalize_graph(_A     ,  _A     )
           lowerCamelCase   :      str			 =					len(_A     )
           lowerCamelCase   :      str			 =					None







    def     _lowercase     (    self     ,  UpperCamelCase__     ,  UpperCamelCase__     )     ->      Optional[Any]:
           if sources is int:
                  lowerCamelCase   :      int			 =					[sources]
           if sinks is int:
                  lowerCamelCase   :      Any			 =					[sinks]

           if len(_A     ) == 0 or len(_A     ) == 0:
                  return

           lowerCamelCase   :      List[Any]			 =					sources[0]
           lowerCamelCase   :      Tuple			 =					sinks[0]

           # make fake vertex if there are more
           # than one source or sink
           if len(_A     ) > 1 or len(_A     ) > 1:
                  lowerCamelCase   :      Optional[int]			 =					0
                  for i in sources:
                         max_input_flow += sum(self.graph[i]     )

                  lowerCamelCase   :      List[str]			 =					len(self.graph     ) + 1
                  for room in self.graph:
                         room.insert(0     ,  0     )
                  self.graph.insert(0     ,  [0] * size     )
                  for i in sources:
                         lowerCamelCase   :      Any			 =					max_input_flow
                  lowerCamelCase   :      Union[str, Any]			 =					0

                  lowerCamelCase   :      Optional[int]			 =					len(self.graph     ) + 1
                  for room in self.graph:
                         room.append(0     )
                  self.graph.append([0] * size     )
                  for i in sinks:
                         lowerCamelCase   :      Dict			 =					max_input_flow
                  lowerCamelCase   :      Optional[Any]			 =					size - 1







    def     _lowercase     (    self     )     ->      Any:
           if self.maximum_flow_algorithm is None:
                  raise Exception("You need to set maximum flow algorithm before."     )
           if self.source_index is None or self.sink_index is None:
                  return 0

           self.maximum_flow_algorithm.execute()
           return self.maximum_flow_algorithm.getMaximumFlow()







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      Tuple:
           lowerCamelCase   :      Any			 =					algorithm(self     )




class 		UpperCamelCase__	:

    '''simple docstring'''



    def __init__(    self     ,  UpperCamelCase__     )     ->      List[str]:
           lowerCamelCase   :      str			 =					flow_network
           lowerCamelCase   :      int			 =					flow_network.verticesCount
           lowerCamelCase   :      Any			 =					flow_network.sourceIndex
           lowerCamelCase   :      Tuple			 =					flow_network.sinkIndex
           # it's just a reference, so you shouldn't change
           # it in your algorithms, use deep copy before doing that
           lowerCamelCase   :      Tuple			 =					flow_network.graph
           lowerCamelCase   :      List[str]			 =					False







    def     _lowercase     (    self     )     ->      Tuple:
           if not self.executed:
                  self._algorithm()
                  lowerCamelCase   :      Any			 =					True







    def     _lowercase     (    self     )     ->      Optional[Any]:
           pass




class 		UpperCamelCase__	(snake_case__     ):

    '''simple docstring'''



    def __init__(    self     ,  UpperCamelCase__     )     ->      str:
           super().__init__(_A     )
           # use this to save your result
           lowerCamelCase   :      List[Any]			 =					-1







    def     _lowercase     (    self     )     ->      Optional[Any]:
           if not self.executed:
                  raise Exception("You should execute algorithm before using its result!"     )

           return self.maximum_flow




class 		UpperCamelCase__	(snake_case__     ):

    '''simple docstring'''



    def __init__(    self     ,  UpperCamelCase__     )     ->      int:
           super().__init__(_A     )

           lowerCamelCase   :      Any			 =					[[0] * self.verticies_count for i in range(self.verticies_count     )]

           lowerCamelCase   :      str			 =					[0] * self.verticies_count
           lowerCamelCase   :      List[str]			 =					[0] * self.verticies_count







    def     _lowercase     (    self     )     ->      Tuple:
           lowerCamelCase   :      Any			 =					self.verticies_count

           # push some substance to graph
           for nextvertex_index, bandwidth in enumerate(self.graph[self.source_index]     ):
                  self.preflow[self.source_index][nextvertex_index] += bandwidth
                  self.preflow[nextvertex_index][self.source_index] -= bandwidth
                  self.excesses[nextvertex_index] += bandwidth

           # Relabel-to-front selection rule
           lowerCamelCase   :      Optional[Any]			 =					[
               i
               for i in range(self.verticies_count     )
               if i != self.source_index and i != self.sink_index
           ]

           # move through list
           lowerCamelCase   :      Union[str, Any]			 =					0
           while i < len(_A     ):
                  lowerCamelCase   :      int			 =					vertices_list[i]
                  lowerCamelCase   :      Dict			 =					self.heights[vertex_index]
                  self.process_vertex(_A     )
                  if self.heights[vertex_index] > previous_height:
                         # if it was relabeled, swap elements
                         # and start from 0 index
                         vertices_list.insert(0     ,  vertices_list.pop(_A     )     )
                         lowerCamelCase   :      int			 =					0
                  else:
                         i += 1

           lowerCamelCase   :      Optional[Any]			 =					sum(self.preflow[self.source_index]     )







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      List[str]:
           while self.excesses[vertex_index] > 0:
                  for neighbour_index in range(self.verticies_count     ):
                         # if it's neighbour and current vertex is higher
                         if (
                             self.graph[vertex_index][neighbour_index]
                             - self.preflow[vertex_index][neighbour_index]
                             > 0
                             and self.heights[vertex_index] > self.heights[neighbour_index]
                         ):
                                self.push(_A     ,  _A     )

                  self.relabel(_A     )







    def     _lowercase     (    self     ,  UpperCamelCase__     ,  UpperCamelCase__     )     ->      Tuple:
           lowerCamelCase   :      Union[str, Any]			 =					min(
               self.excesses[from_index]     ,  self.graph[from_index][to_index] - self.preflow[from_index][to_index]     ,  )
           self.preflow[from_index][to_index] += preflow_delta
           self.preflow[to_index][from_index] -= preflow_delta
           self.excesses[from_index] -= preflow_delta
           self.excesses[to_index] += preflow_delta







    def     _lowercase     (    self     ,  UpperCamelCase__     )     ->      Optional[Any]:
           lowerCamelCase   :      List[Any]			 =					None
           for to_index in range(self.verticies_count     ):
                  if (
                      self.graph[vertex_index][to_index]
                      - self.preflow[vertex_index][to_index]
                      > 0
                  ) and (min_height is None or self.heights[to_index] < min_height):
                         lowerCamelCase   :      Union[str, Any]			 =					self.heights[to_index]

           if min_height is not None:
                  lowerCamelCase   :      List[str]			 =					min_height + 1


if __name__ == "__main__":
       SCREAMING_SNAKE_CASE__       :      int  =   [0]
       SCREAMING_SNAKE_CASE__       :      Any  =   [3]
       # graph = [
       #     [0, 0, 4, 6, 0, 0],
       #     [0, 0, 5, 2, 0, 0],
       #     [0, 0, 0, 0, 4, 4],
       #     [0, 0, 0, 0, 6, 6],
       #     [0, 0, 0, 0, 0, 0],
       #     [0, 0, 0, 0, 0, 0],
       # ]
       SCREAMING_SNAKE_CASE__       :      List[str]  =   [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]

       # prepare our network
       SCREAMING_SNAKE_CASE__       :      int  =   FlowNetwork(graph, entrances, exits)
       # set algorithm
       flow_network.set_maximum_flow_algorithm(PushRelabelExecutor)
       # and calculate
       SCREAMING_SNAKE_CASE__       :      Optional[Any]  =   flow_network.find_maximum_flow()

       print(f'''maximum flow is {maximum_flow}''')













from heapq import heappop, heappush

import numpy as np







def  _SCREAMING_SNAKE_CASE				(   a					,						a					,						a					,						a					,						)      ->      tuple[float | int, list[tuple[int, int]]]:
					__A    ,				__A	:						int       =				grid.shape
					__A	:						Any       =				[-1, 1, 0, 0]
					__A	:						Optional[Any]       =				[0, 0, -1, 1]
					if allow_diagonal:
										dx += [-1, -1, 1, 1]
										dy += [-1, 1, -1, 1]

					__A    ,				__A	:						Optional[int]       =				[(0, source)], set()
					__A	:						Any       =				np.full((rows, cols)					,						np.inf  )
					__A	:						Any       =				0
					__A	:						Any       =				np.empty((rows, cols)					,						dtype=a  )
					__A	:						Optional[Any]       =				None

					while queue:
										((__A)    ,				(__A))	:						List[str]       =				heappop(a  )
										if (x, y) in visited:
															continue
										visited.add((x, y)  )

										if (x, y) == destination:
															__A	:						int       =				[]
															while (x, y) != source:
																				path.append((x, y)  )
																				__A    ,				__A	:						Optional[int]       =				predecessors[x, y]
															path.append(a  )  # add the source manually
															path.reverse()
															return matrix[destination], path

										for i in range(len(a  )  ):
															__A    ,				__A	:						Union[str, Any]       =				x + dx[i], y + dy[i]
															if 0 <= nx < rows and 0 <= ny < cols:
																				__A	:						Optional[int]       =				grid[nx][ny]
																				if next_node == 1 and matrix[nx, ny] > dist + 1:
																									heappush(a					,						(dist + 1, (nx, ny))  )
																									__A	:						List[Any]       =				dist + 1
																									__A	:						Union[str, Any]       =				(x, y)

					return np.inf, []


if __name__ == "__main__":
				import doctest

				doctest.testmod()




