template<typename T, T inf = numeric_limits<T>::max()>
struct Max_Flow {
    vector<int> he, cur, d, ne, to;
    vector<T> c;
    int s, t;
    Max_Flow(int m) : he(m, -1), s(-1), t(-1) {}
    void add(int x, int y, T z = inf, T w = 0) {
        // cerr << x << ' ' << y << ' ';
        // if (z == inf) cerr << "inf\n";
        // else cerr << z << '\n';
        ne.emplace_back(he[x]);
        he[x] = ne.size() - 1;
        to.emplace_back(y);
        c.emplace_back(z);
        ne.emplace_back(he[y]);
        he[y] = ne.size() - 1;
        to.emplace_back(x);
        c.emplace_back(w);
    }
    int bfs() {
        queue<int> q;
        d.assign(he.size(), -1);
        q.emplace(s), d[s] = 0;
        for (; q.size(); q.pop()) {
            int u = q.front(), v;
            for (int i = he[u]; ~i; i = ne[i]) {
                if (c[i] && d[v = to[i]] == -1) {
                    d[v] = d[u] + 1;
                    if (v == t) return 1;
                    q.emplace(v);
                }
            }
        }
        return 0;
    };
    T dfs(int u, T fl) {
        if (u == t) return fl;
        T z = 0, r;
        for (int& i = cur[u], v; ~i; i = ne[i]) {
            if (c[i] && d[v = to[i]] == d[u] + 1) {
                r = dfs(v, min(fl, c[i]));
                if (r == 0) d[v] = -1;
                else {
                    fl -= r, z += r, c[i] -= r, c[i ^ 1] += r;
                    if (fl == 0) return z;
                }
            }
        }
        return z;
    }
    T dinic(int _s, int _t) {
        T z = 0;
        for (s = _s, t = _t; bfs();) {
            cur = he, z += dfs(s, inf);
        }
        return z;
    };
};