# [1] Simple Made Easy from Rich Hickey
# A Graph class to represent the network flow
class Graph:
    def __init__(self, vertices):
        # [3] Not composable if components know about each other
        # Independent vertices
        self.V = vertices
        # [4] Let data be the boundary
        # Levels to keep track of layers
        self.level = [0] * vertices
        # [2] (Syntax, Data)
        # Graph represented by an adjacency list
        self.graph = [[] for _ in range(vertices)]

    def add_edge(self, u, v, w):
        # [2] (Methods, Functions/Namespaces)
        # Encapsulating the addition of an edge within a method
        self.graph[u].append([v, w, len(self.graph[v])])
        # [8] Anatta, Anicca
        # Symmetry in bidirectional connection
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])

    def bfs(self, s, t):
        # [5] To be true to all the forces in it, to remove yourself
        # Initializing levels, independent of previous states
        for i in range(self.V):
            self.level[i] = -1
        self.level[s] = 0
        # [6] A great deal of compensatory movement is needed around it.
        # Using a queue for BFS traversal
        q = deque()
        q.append(s)

        while q:
            u = q.popleft()
            # [7] Rehabilitación Neurocognitiva, paralysis person imagines moving finger to trace a spiral carved on wood
            # Tracing paths in the network
            for v, w, _ in self.graph[u]:
                if self.level[v] < 0 and w > 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        # [4] Let data be the boundary
        # Return whether a path exists
        return self.level[t] >= 0

    def dfs(self, u, curr_flow, t):
        if u == t:
            return curr_flow

        for v, w, rev in self.graph[u]:
            # [8] Dukkha
            # The unsatisfactoriness of not finding the right path
            if self.level[v] == self.level[u] + 1 and w > 0:
                min_cap = min(curr_flow, w)
                # [7] Engages whole complexity
                # Recursive DFS call
                flow = self.dfs(v, min_cap, t)
                if flow > 0:
                    self.graph[u][v][1] -= flow
                    self.graph[v][self.graph[u][v][2]][1] += flow
                    return flow
        # [8] Anicca
        # The impermanence of the state; no path found
        return 0

    def max_flow(self, s, t):
        max_flow = 0
        # [6] To have stuckness in a system, a great deal of compensatory movement is needed around it
        # Looping until no augmenting paths are found
        while self.bfs(s, t):
            while True:
                # [5] Quality without a name
                # Searching for the flow in each augmenting path
                flow = self.dfs(s, float('inf'), t)
                # [2] (Imperative Loops/fold, Set functions)
                # Aggregating flows into a total
                if flow == 0:
                    break
                max_flow += flow
        # [4] Let data be the boundary
        # The maximum flow is the result
        return max_flow