



"""simple docstring"""





class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						Dict	,       _UpperCAmelCase    :						int	,       _UpperCAmelCase    :						Optional[Any]	,       _UpperCAmelCase    :						str					)				->		Union[str, Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							None
             UpperCAmelCase_    				=							None
             UpperCAmelCase_    				=							graph

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



       def   lowercase__       (							self    :						Optional[Any]	,       _UpperCAmelCase    :						Tuple	,       _UpperCAmelCase    :						Dict					)				->		str:


             '''simple docstring'''




             if sources is int:
                   UpperCAmelCase_    				=							[sources]
             if sinks is int:
                   UpperCAmelCase_    				=							[sinks]

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

             UpperCAmelCase_    				=							sources[0]
             UpperCAmelCase_    				=							sinks[0]

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

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

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



       def   lowercase__       (							self    :						List[str]					)				->		Dict:


             '''simple docstring'''




             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    :						Any	,       _UpperCAmelCase    :						Optional[int]					)				->		List[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							algorithm(self					)



class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						Dict	,       _UpperCAmelCase    :						Union[str, Any]					)				->		List[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							flow_network
             UpperCAmelCase_    				=							flow_network.verticesCount
             UpperCAmelCase_    				=							flow_network.sourceIndex
             UpperCAmelCase_    				=							flow_network.sinkIndex
             # it's just a reference, so you shouldn't change
             # it in your algorithms, use deep copy before doing that
             UpperCAmelCase_    				=							flow_network.graph
             UpperCAmelCase_    				=							False



       def   lowercase__       (							self    :						str					)				->		Dict:


             '''simple docstring'''




             if not self.executed:
                   self._algorithm()
                   UpperCAmelCase_    				=							True







       def   lowercase__       (							self    :						Any					)				->		Dict:


             '''simple docstring'''




             pass



class    lowercase__     (					_SCREAMING_SNAKE_CASE   ):







       '''simple docstring'''


       def __init__(							self    :						List[str]	,       _UpperCAmelCase    :						Optional[Any]					)				->		List[Any]:


             '''simple docstring'''




             super().__init__(A_					)
             # use this to save your result
             UpperCAmelCase_    				=							-1







       def   lowercase__       (							self    :						Union[str, Any]					)				->		Optional[int]:


             '''simple docstring'''




             if not self.executed:
                   raise Exception("You should execute algorithm before using its result!"					)

             return self.maximum_flow



class    lowercase__     (					_SCREAMING_SNAKE_CASE   ):







       '''simple docstring'''


       def __init__(							self    :						Optional[int]	,       _UpperCAmelCase    :						int					)				->		List[str]:


             '''simple docstring'''




             super().__init__(A_					)

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

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



       def   lowercase__       (							self    :						Any					)				->		List[str]:


             '''simple docstring'''




             UpperCAmelCase_    				=							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
             UpperCAmelCase_    				=							[
                 i
                 for i in range(self.verticies_count					)
                 if i != self.source_index and i != self.sink_index
             ]

             # move through list
             UpperCAmelCase_    				=							0
             while i < len(A_					):
                   UpperCAmelCase_    				=							vertices_list[i]
                   UpperCAmelCase_    				=							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_					)					)
                         UpperCAmelCase_    				=							0
                   else:
                         i += 1

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



       def   lowercase__       (							self    :						str	,       _UpperCAmelCase    :						str					)				->		List[Any]:


             '''simple docstring'''




             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    :						int	,       _UpperCAmelCase    :						Optional[int]	,       _UpperCAmelCase    :						Tuple					)				->		Dict:


             '''simple docstring'''




             UpperCAmelCase_    				=							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    :						Any	,       _UpperCAmelCase    :						List[Any]					)				->		Tuple:


             '''simple docstring'''




             UpperCAmelCase_    				=							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):
                         UpperCAmelCase_    				=							self.heights[to_index]

             if min_height is not None:
                   UpperCAmelCase_    				=							min_height + 1


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

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

 print(F"maximum flow is {maximum_flow}")









"""simple docstring"""





from __future__ import annotations
def      a__			(   lowerCAmelCase__   ):
      if len(lowerCAmelCase__   ) == 0:
            return []
      UpperCAmelCase_				,					UpperCAmelCase_    				=							min(lowerCAmelCase__   ), max(lowerCAmelCase__   )
      UpperCAmelCase_    				=							int(max_value - min_value   ) + 1
      UpperCAmelCase_    				=							[[] for _ in range(lowerCAmelCase__   )]

      for i in my_list:
            buckets[int(i - min_value   )].append(lowerCAmelCase__   )

      return [v for bucket in buckets for v in sorted(lowerCAmelCase__   )]


if __name__ == "__main__":
  from doctest import testmod

  testmod()
  assert bucket_sort([4, 5, 3, 2, 1]) == [1, 2, 3, 4, 5]
  assert bucket_sort([0, 1, -10, 15, 2, -2]) == [-10, -2, 0, 1, 2, 15]




