Dinic

class Dinic{
    struct Edge{
        int to;
        int c;
        int flow;
    };

    vector<Edge> edges;
    vector<vector<int>> g;
    vector<int> lvl;
    int s,t;
    const int INF = 100000;
    const int VCOUNT;

public:
    Dinic(int VCOUNT) : VCOUNT(VCOUNT), g(VCOUNT), lvl(VCOUNT){}

    void addEdge(int u, int v, int cap){
        Edge dir = {v,cap,0};
        Edge aug = {u,0,0};
        g[u].push_back(edges.size());
        edges.push_back(dir);
        g[v].push_back(edges.size());
        edges.push_back(aug);
    }

    void clearAll(){
        for(auto &a : g)a.clear();
        edges.clear();
    }

    void clearFlow(){
        for(auto &e : edges)e.flow = 0;
    }

    bool BFS(){
        fill(lvl.begin(), lvl.end(), -1);
        queue<int> q;
        q.push(s);
        lvl[s] = 0;

        while(!q.empty()){
            int v = q.front(); q.pop();
            if(v == t) break;

            for(auto u : g[v]){
                Edge &e = edges[u];
                if(lvl[e.to] < 0 && e.flow < e.c){
                    lvl[e.to] = lvl[v] + 1;
                    q.push(e.to);
                }
            }
        }

        return lvl[t] != -1;
    }

    int DFS(int v, int minFlow){
        if(v == t || minFlow == 0) return minFlow;
        int flow = 0;

        for(auto adj : g[v]){
            Edge &e = edges[adj];
            if(lvl[e.to] == lvl[v]+1 && e.flow < e.c){
                int ret = DFS(e.to, min(minFlow, e.c - e.flow));
                if(ret > 0){
                    e.flow += ret;
                    edges[adj^1].flow -= ret;
                    flow += ret;
                    minFlow -= ret;
                    if(ret <= 0)break;
                }
            }
        }

        return flow;
    }

    int maxFlow(int s, int t){
        this->s = s;
        this->t = t;

        int mf = 0;
        while(BFS()){
            int f = DFS(s, INF);
            mf += f;
            if(f == 0) break;
        }

        return mf;
    }
};