import java.util.ArrayList;
import java.util.Arrays;

public class Graph {
    final static int INF = Integer.MAX_VALUE / 2;

    public static class Edge {
        final int to;
        Edge rev;
        int remain;
        final boolean isReverse;

        private Edge(int to, int remain, boolean isReverse) {
            this.to = to;
            this.remain = remain;
            this.isReverse = isReverse;
        }
    }

    public final int n;
    public Integer defaultS, defaultT;
    public ArrayList<Edge>[] g;

    public Graph(int n) {
        this.n = n;
        g = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        used = new int[n];
        q = new int[n];
        layer = new int[n];
        start = new int[n];
    }

    public void addEdge(int from, int to, int w) {
        Edge e1 = new Edge(to, w, false);
        Edge e2 = new Edge(from, 0, true);
        e1.rev = e2;
        e2.rev = e1;
        g[from].add(e1);
        g[to].add(e2);
    }

    int[] q;
    int q1, q2;

    int[] layer;

    int version = 1;
    int[] used;
    int[] start;

    boolean bfs(int s, int t) {
        Arrays.fill(layer, -1);
        layer[s] = 0;
        q1 = q2 = 0;
        q[q2++] = s;
        while (q1 != q2) {
            int v = q[q1++];
            for (int i = 0; i < g[v].size(); i++) {
                Edge e = g[v].get(i);
                if (e.remain == 0) {
                    continue;
                }
                if (layer[e.to] == -1) {
                    layer[e.to] = layer[v] + 1;
                    q[q2++] = e.to;
                }
            }
        }
        return layer[t] != -1;
    }

    int dfs(int v, int to, int threshold) {
        used[v] = version;
        if (v == to) {
            return threshold;
        }
        for (; start[v] < g[v].size(); start[v]++) {
            Edge e = g[v].get(start[v]);
            if (used[e.to] == version || layer[e.to] != layer[v] + 1 || e.remain == 0) {
                continue;
            }
            int t = dfs(e.to, to, Math.min(threshold, e.remain));
            if (t != 0) {
                e.remain -= t;
                e.rev.remain += t;
                return t;
            }
        }
        return 0;
    }

    int maxFlow() {
        return maxFlow(defaultS, defaultT);
    }

    int maxFlow(int from, int to) {
        if (from == to) {
            return Integer.MAX_VALUE / 2;
        }
        int res = 0;
        while (bfs(from, to)) {
            version++;
            int add;
            Arrays.fill(start, 0);
            while ((add = dfs(from, to, INF)) > 0) {
                res += add;
                version++;
            }
        }
        return res;
    }
}
