



'''simple docstring'''





class 				snake_case :



       def __init__(				self     ,UpperCAmelCase_     ,UpperCAmelCase_     ,UpperCAmelCase_      )  ->							int:
           lowercase__		       =						None
           lowercase__		       =						None
           lowercase__		       =						graph

           self._normalize_graph(UpperCAmelCase_     ,UpperCAmelCase_      )
           lowercase__		       =						len(UpperCAmelCase_      )
           lowercase__		       =						None



       def 							_a      (				self     ,UpperCAmelCase_     ,UpperCAmelCase_      )  ->							Optional[int]:
           if sources is int:
               lowercase__		       =						[sources]
           if sinks is int:
               lowercase__		       =						[sinks]

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

           lowercase__		       =						sources[0]
           lowercase__		       =						sinks[0]

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

               lowercase__		       =						len(self.graph      ) + 1
               for room in self.graph:
                   room.insert(0     ,0      )
               self.graph.insert(0     ,[0] * size      )
               for i in sources:
                   lowercase__		       =						max_input_flow
               lowercase__		       =						0

               lowercase__		       =						len(self.graph      ) + 1
               for room in self.graph:
                   room.append(0      )
               self.graph.append([0] * size      )
               for i in sinks:
                   lowercase__		       =						max_input_flow
               lowercase__		       =						size - 1



       def 							_a      (				self      )  ->							Union[str, 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 							_a      (				self     ,UpperCAmelCase_      )  ->							Dict:
           lowercase__		       =						algorithm(self      )





class 				snake_case :



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



       def 							_a      (				self      )  ->							List[Any]:
           if not self.executed:
               self._algorithm()
               lowercase__		       =						True







       def 							_a      (				self      )  ->							Dict:
           pass





class 				snake_case (UpperCamelCase   ):



       def __init__(				self     ,UpperCAmelCase_      )  ->							Tuple:
           super().__init__(UpperCAmelCase_      )
           # use this to save your result
           lowercase__		       =						-1







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

           return self.maximum_flow





class 				snake_case (UpperCamelCase   ):



       def __init__(				self     ,UpperCAmelCase_      )  ->							Dict:
           super().__init__(UpperCAmelCase_      )

           lowercase__		       =						[[0] * self.verticies_count for i in range(self.verticies_count      )]

           lowercase__		       =						[0] * self.verticies_count
           lowercase__		       =						[0] * self.verticies_count



       def 							_a      (				self      )  ->							Optional[int]:
           lowercase__		       =						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
           lowercase__		       =						[
               i
               for i in range(self.verticies_count      )
               if i != self.source_index and i != self.sink_index
           ]

           # move through list
           lowercase__		       =						0
           while i < len(UpperCAmelCase_      ):
               lowercase__		       =						vertices_list[i]
               lowercase__		       =						self.heights[vertex_index]
               self.process_vertex(UpperCAmelCase_      )
               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(UpperCAmelCase_      )      )
                   lowercase__		       =						0
               else:
                   i += 1

           lowercase__		       =						sum(self.preflow[self.source_index]      )



       def 							_a      (				self     ,UpperCAmelCase_      )  ->							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(UpperCAmelCase_     ,UpperCAmelCase_      )

               self.relabel(UpperCAmelCase_      )



       def 							_a      (				self     ,UpperCAmelCase_     ,UpperCAmelCase_      )  ->							str:
           lowercase__		       =						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 							_a      (				self     ,UpperCAmelCase_      )  ->							Optional[Any]:
           lowercase__		       =						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):
                   lowercase__		       =						self.heights[to_index]

           if min_height is not None:
               lowercase__		       =						min_height + 1


if __name__ == "__main__":
 SCREAMING_SNAKE_CASE__      					=     [0]
 SCREAMING_SNAKE_CASE__      					=     [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__      					=     [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]

 # prepare our network
 SCREAMING_SNAKE_CASE__      					=     FlowNetwork(graph, entrances, exits)
 # set algorithm
 flow_network.set_maximum_flow_algorithm(PushRelabelExecutor)
 # and calculate
 SCREAMING_SNAKE_CASE__      					=     flow_network.find_maximum_flow()

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









'''simple docstring'''





def        lowerCamelCase  (				_snake_case  :						int     ,_snake_case  :						int       ):





    '''simple docstring'''


    return x if y == 0 else greatest_common_divisor(_snake_case     ,x % y       )




def        lowerCamelCase  (				_snake_case  :						int     ,_snake_case  :						int       ):





    '''simple docstring'''


    return (x * y) // greatest_common_divisor(_snake_case     ,_snake_case       )




def        lowerCamelCase  (				_snake_case  :						int = 20       ):





    '''simple docstring'''


    lowercase__		       =						1
    for i in range(1     ,n + 1       ):
        lowercase__		       =						lcm(_snake_case     ,_snake_case       )
    return g


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




