

_UpperCamelCase			       =			float('''inf''')



class     lowercase						:



 '''simple docstring'''


 def __init__(self       ,       __a ) ->					List[Any]:






  """simple docstring"""





  UpperCAmelCase__							=				[0] * n
  UpperCAmelCase__							=				[0] * n
  UpperCAmelCase__							=				[0] * n
  UpperCAmelCase__							=				[[] for _ in range(__a )]




 def   UpperCamelCase__							(self       ,       __a       ,       __a       ,       __a       ,       __a=0 ) ->					Any:






  """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   UpperCamelCase__							(self       ,       __a       ,       __a       ,       __a ) ->					Union[str, Any]:






  """simple docstring"""





  if vertex == sink or not flow:
   return flow

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




 def   UpperCamelCase__							(self       ,       __a       ,       __a ) ->					Any:






  """simple docstring"""





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

    UpperCAmelCase__							=				self.depth_first_search(__a       ,       __a       ,       __a )
    while p:
     flow += p
     UpperCAmelCase__							=				self.depth_first_search(__a       ,       __a       ,       __a )

    if not self.lvl[sink]:
     break

  return flow
_UpperCamelCase			       =			Dinic(10)
_UpperCamelCase			       =			0
_UpperCamelCase			       =			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))






def 						UpperCamelCase_(			snake_case__:  list   )       -> list:
 UpperCAmelCase__							=				len(snake_case__   )

 # Set the gap value to be decreased by a factor of 1.3
 # after each iteration
 UpperCAmelCase__							=				1.3

 # Continue sorting until the gap is 1
 while gap > 1:
  # Decrease the gap value
  UpperCAmelCase__							=				int(gap / shrink   )

  # Sort the elements using insertion sort
  for i in range(snake_case__  ,    len(snake_case__   )   ):
   UpperCAmelCase__							=				collection[i]
   UpperCAmelCase__							=				i
   while j >= gap and collection[j - gap] > temp:
    UpperCAmelCase__							=				collection[j - gap]
    j -= gap
   UpperCAmelCase__							=				temp

 return collection


if __name__ == "__main__":
 import doctest

 doctest.testmod()



