最大流

template <class T>
struct Flow {
    const int n;
    vector<pair<int, T>> edges;
    vector<vector<int>> adj;
    vector<pair<int, int>> pre;
    vector<T> f;
    Flow(int n) : n(n), adj(n) {}
    T bfs(int s, int t) {
        pre.assign(n, {-1, -1});
        f.assign(n, 0);
        f[s] = numeric_limits<T>::max();
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            if (u == t) {
                break;
            }
            for (auto &idx : adj[u]) {
                auto [to, w] = edges[idx];
                if (to == s) continue;
                if (w <= 0) continue;
                if (pre[to].second != -1) continue;
                pre[to] = {idx, u};
                f[to] = min(f[u], w);
                que.push(to);
            }
        }
        if (pre[t].second == -1) return -1;
        return f[t];
    }
    void add(int u, int v, T c) {
        adj[u].push_back(edges.size());
        edges.push_back({v, c});
        adj[v].push_back(edges.size());
        edges.push_back({u, 0});
    }

    T edmondsKarp(int s, int t) {
        T ans = 0;
        while (true) {
            T flow = bfs(s, t);
            if (flow == -1) {
                break;
            }
            int cur = t;
            while (cur != s) {
                auto [idx, fa] = pre[cur];
                edges[idx].second -= flow;
                edges[idx ^ 1].second += flow;
                cur = fa;
            }
            ans += flow;
        }
        return ans;
    }
}; // Flow

template <class T>
struct Flow {
    const int n;
    vector<pair<int, T>> edges;
    vector<vector<int>> adj;
    vector<int> cur, dep;
    Flow(int n) : n(n), adj(n) {}
    bool bfs(int s, int t) {
        dep.assign(n, -1);
        queue<int> q;
        dep[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &idx : adj[u]) {
                auto [to, w] = edges[idx];
                if (w > 0 && dep[to] == -1) {
                    dep[to] = dep[u] + 1;
                    if (to == t) {
                        return true;
                    }
                    q.push(to);
                }
            }
        }
        return false;
    }
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        T res = f;
        for (int &i = cur[u] ; i < (int) adj[u].size() ; i++) {
            int idx = adj[u][i];
            auto [to, w] = edges[idx];
            if (w > 0 and dep[to] == dep[u] + 1) {
                T out = dfs(to, t, min(res, w));
                edges[idx].second -= out;
                edges[idx ^ 1].second += out;
                res -= out;
                if (res == 0) {
                    return f;
                }
            }
        }
        return f - res;
    }
    void add(int u, int v, T c) {
        adj[u].push_back(edges.size());
        edges.push_back({v, c});
        adj[v].push_back(edges.size());
        edges.push_back({u, 0});
    }

    T dinic(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, numeric_limits<T>::max());
        }
        return ans;
    }
}; // Flow