



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






def 					__lowerCAmelCase		(  __lowerCamelCase	:    int				,   __lowerCamelCase	:    int				,   __lowerCamelCase	:    int				,   __lowerCamelCase	:    Optional[Any]	)  ->						Optional[int]:
					# Return True if there is node that has not iterated.
					__lowerCAmelCase	   =[False] * len(__lowerCamelCase	)
					__lowerCAmelCase	   =[s]
					__lowerCAmelCase	   =True

					while queue:
										__lowerCAmelCase	   =queue.pop(0	)
										for ind in range(len(graph[u]	)	):
															if visited[ind] is False and graph[u][ind] > 0:
																				queue.append(__lowerCamelCase	)
																				__lowerCAmelCase	   =True
																				__lowerCAmelCase	   =u

					return visited[t]






def 					__lowerCAmelCase		(  __lowerCamelCase	:    List[str]				,   __lowerCamelCase	:    Dict				,   __lowerCamelCase	:    List[str]	)  ->						Tuple:
					__lowerCAmelCase	   =[-1] * (len(__lowerCamelCase	))
					__lowerCAmelCase	   =0
					__lowerCAmelCase	   =[]
					__lowerCAmelCase	   =[i[:] for i in graph]  # Record original cut, copy.
					while bfs(__lowerCamelCase				,   __lowerCamelCase				,   __lowerCamelCase				,   __lowerCamelCase	):
										__lowerCAmelCase	   =float("""Inf"""	)
										__lowerCAmelCase	   =sink

										while s != source:
															# Find the minimum value in select path
															__lowerCAmelCase	   =min(__lowerCamelCase				,   graph[parent[s]][s]	)
															__lowerCAmelCase	   =parent[s]

										max_flow += path_flow
										__lowerCAmelCase	   =sink

										while v != source:
															__lowerCAmelCase	   =parent[v]
															graph[u][v] -= path_flow
															graph[v][u] += path_flow
															__lowerCAmelCase	   =parent[v]

					for i in range(len(__lowerCamelCase	)	):
										for j in range(len(graph[0]	)	):
															if graph[i][j] == 0 and temp[i][j] > 0:
																				res.append((i, j)	)

					return res


if __name__ == "__main__":
				print(mincut(test_graph, source=0, sink=5))









def 					__lowerCAmelCase		(  __lowerCamelCase	:    list				,   __lowerCamelCase	:    int				,   __lowerCamelCase	:    int = 0				,   __lowerCamelCase	:    int = 0	)  ->						int:
					__lowerCAmelCase	   =right or len(__lowerCamelCase	) - 1
					if left > right:
										return -1
					elif list_data[left] == key:
										return left
					elif list_data[right] == key:
										return right
					else:
										return search(__lowerCamelCase				,   __lowerCamelCase				,   left + 1				,   right - 1	)


if __name__ == "__main__":
				import doctest

				doctest.testmod()




