






'''simple docstring'''
def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    Union[str, Any]           =     [False] * len(_UpperCamelCase							)
   lowercase_	:    Optional[Any]           =     []
   queue.append(_UpperCamelCase							)
   lowercase_	:    Dict           =     True

   while queue:
      lowercase_	:    Any           =     queue.pop(0							)
      for ind in range(len(graph[u]							)							):
         if visited[ind] is False and graph[u][ind] > 0:
            queue.append(_UpperCamelCase							)
            lowercase_	:    Tuple           =     True
            lowercase_	:    List[str]           =     u

   return visited[t]




def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    int           =     [-1] * (len(_UpperCamelCase							))
   lowercase_	:    Any           =     0
   while bfs(_UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase							):
      lowercase_	:    Optional[int]           =     float("Inf"							)
      lowercase_	:    List[Any]           =     sink

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

      max_flow += path_flow
      lowercase_	:    Dict           =     sink

      while v != source:
         lowercase_	:    Union[str, Any]           =     parent[v]
         graph[u][v] -= path_flow
         graph[v][u] += path_flow
         lowercase_	:    Any           =     parent[v]
   return max_flow


UpperCamelCase__ =			[
    [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],
]

UpperCamelCase__,     UpperCamelCase__ =			0, 5





print(ford_fulkerson(graph, source, sink))












'''simple docstring'''
def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   return [
       {
           0: [1, 2],
           1: [0, 2],
           2: [0, 1, 3, 5],
           3: [2, 4],
           4: [3],
           5: [2, 6, 8],
           6: [5, 7],
           7: [6, 8],
           8: [5, 7],
       },
       {
           0: [6],
           1: [9],
           2: [4, 5],
           3: [4],
           4: [2, 3],
           5: [2],
           6: [0, 7],
           7: [6],
           8: [],
           9: [1],
       },
       {
           0: [4],
           1: [6],
           2: [],
           3: [5, 6, 7],
           4: [0, 6],
           5: [3, 8, 9],
           6: [1, 3, 4, 7],
           7: [3, 6, 8, 9],
           8: [5, 7],
           9: [5, 7],
       },
       {
           0: [1, 3],
           1: [0, 2, 4],
           2: [1, 3, 4],
           3: [0, 2, 4],
           4: [1, 2, 3],
       },
   ][index]




def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    Dict           =     0
   lowercase_	:    Optional[Any]           =     len(_UpperCamelCase							)  # No of vertices in graph
   lowercase_	:    Union[str, Any]           =     [0] * n
   lowercase_	:    Optional[int]           =     [False] * n

   def dfs(_UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase							):
      lowercase_	:    Union[str, Any]           =     True
      lowercase_	:    Dict           =     id_
      id_ += 1
      for to in graph[at]:
         if to == parent:
            pass
         elif not visited[to]:
            dfs(_UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase						,		id_							)
            lowercase_	:    str           =     min(low[at]						,		low[to]							)
            if id_ <= low[to]:
               bridges.append((at, to) if at < to else (to, at)							)
         else:
            # This edge is a back edge and cannot be a bridge
            lowercase_	:    Optional[int]           =     min(low[at]						,		low[to]							)

   lowercase_	:    list[tuple[int, int]]           =     []
   for i in range(_UpperCamelCase							):
      if not visited[i]:
         dfs(_UpperCamelCase						,		-1						,		_UpperCamelCase						,		id_							)
   return bridges


if __name__ == "__main__":
 import doctest

 doctest.testmod()




