template <int N> struct Dinic
{
    const int INF = 2e9 + 7;
    struct E { int to, cap, rev; };
    vector<E> G[N];
    int dep[N], cur[N];
    inline void add(int x, int y, int c)
    {
        G[x].push_back({ y, c, (int)G[y].size() });
        G[y].push_back({ x, 0, (int)G[x].size() - 1 });
    }
    void bfs(int s)
    {
        queue<int> q; memset(dep, -1, sizeof dep);
        for (dep[s] = 0, q.push(s);q.size();)
        {
            int x = q.front(); q.pop();
            for (auto& e : G[x]) if (e.cap > 0 && dep[e.to] < 0)
                dep[e.to] = dep[x] + 1, q.push(e.to);
        }
    }
    int dfs(int x, int t, int f)
    {
        if (x == t) return f;
        for (int& i = cur[x], sz = G[x].size(), d;i < sz;i++)
        {
            auto& e = G[x][i];
            if (e.cap > 0 && dep[x] < dep[e.to])
            {
                if ((d = dfs(e.to, t, min(f, e.cap))) > 0)
                {
                    e.cap -= d, G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int maxflow(int s, int t)
    {
        for (int flow = 0, f;;)
        {
            bfs(s);
            if (dep[t] < 0) return flow;
            memset(cur, 0, sizeof cur);
            while ((f = dfs(s, t, INF)) > 0) flow += f;
        }
    }
};