"""Part 8: maximum flow and minimum cut, by Edmonds and Karp.

Push flow from s to t along shortest augmenting paths (breadth-first search in the residual
graph) until none is left. The value of the flow is then the capacity of the smallest cut
between s and t, and the fields still reachable from s in the residual graph are its s side
(Ford and Fulkerson's max-flow min-cut theorem). Shortest paths bound the number of augmentations
by O(V E) (Edmonds and Karp, 1972).

Capacities can be ints, Fractions or floats; with floats, anything under `eps` counts as empty.
A Network is built once and can then answer many s-t questions, which is what the cutting-plane
loop asks: one minimum cut from the start to every field.
"""
from collections import deque


class Network:
    def __init__(self, n, edges):
        """edges: [(u, v, capacity)], undirected. Each becomes two arcs, 2k: u -> v and
        2k + 1: v -> u, each with the full capacity: an undirected edge carries flow either way."""
        self.n = n
        self.head, self.capacity = [], []
        self.arcs = [[] for _ in range(n)]          # arcs leaving each node
        for u, v, cap in edges:
            if u == v:
                continue
            self.arcs[u].append(len(self.head))
            self.head.append(v)
            self.capacity.append(cap)
            self.arcs[v].append(len(self.head))
            self.head.append(u)
            self.capacity.append(cap)

    def min_cut(self, s, t, enough=None, eps=0):
        """Returns (flow value, set of nodes on s's side of a minimum cut). With `enough`, stops as
        soon as the flow reaches it and returns (value, None): the cut is at least that big."""
        head, arcs = self.head, self.arcs
        residual = self.capacity[:]
        flow = 0
        while True:
            came_by = [-1] * self.n                 # the arc each node was reached by
            came_by[s] = -2
            queue = deque([s])
            while queue and came_by[t] == -1:
                u = queue.popleft()
                for a in arcs[u]:
                    v = head[a]
                    if came_by[v] == -1 and residual[a] > eps:
                        came_by[v] = a
                        queue.append(v)
            if came_by[t] == -1:
                return flow, {v for v in range(self.n) if came_by[v] != -1}
            path, v = [], t
            while v != s:
                a = came_by[v]
                path.append(a)
                v = head[a ^ 1]                     # arc a ^ 1 runs the other way
            push = min(residual[a] for a in path)
            for a in path:
                residual[a] -= push
                residual[a ^ 1] += push
            flow += push
            if enough is not None and flow >= enough - eps:
                return flow, None


def min_cut(n, edges, s, t, enough=None, eps=0):
    """One question on its own: build the network and ask it."""
    return Network(n, edges).min_cut(s, t, enough, eps)