class din{

    struct edge{
        int to;
        int cap;
        int rev;
    };

    public : 
    int n;
    vector<vector<edge>> g;
    vector<int> level;
    vector<int> ite;

    din(int x){
        n = x;
        g.resize(n);
        level.resize(n);
        ite.resize(n);
    }

    void add(int from,int to,int cap){
        g[from].push_back(edge{to,cap,(int)g[to].size()});
        g[to].push_back(edge{from,0,(int)g[from].size()-1});
    }

    bool bfs(int s,int t){
        level.assign(n,-1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(q.size()!=0){
            int pos = q.front();
            q.pop();
            for(const edge& e : g[pos]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[pos]+1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    int dfs(int v,int t,int f){
        if(v==t)return f;
        for(int &i = ite[v];i < (int)g[v].size();i++){
            edge& e = g[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int d = dfs(e.to,t,min(f,e.cap));
                if(d > 0){
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int flow(int s,int t){
        int ans = 0;
        while(1){
            if(!bfs(s,t))break;
            ite.assign(n,0);
            int f = dfs(s,t,INF);
            while(1){
                if(f>0){
                    ans += f;
                    f = dfs(s,t,INF);
                }
                else{
                    break;
                }
            }
            
        }
        return ans;
    }

};

class din{

    struct edge{
        int to;
        int cap;
        int rev;
    };

    public : 
    int n;
    vector<vector<edge>> g;
    vector<int> level;
    vector<int> ite;

    din(int x){
        n = x;
        g.resize(n);
        level.resize(n);
        ite.resize(n);
    }

    void add(int from,int to,int cap){
        g[from].push_back(edge{to,cap,(int)g[to].size()});
        g[to].push_back(edge{from,0,(int)g[from].size()-1});
    }

    bool bfs(int s,int t){
        level.assign(n,-1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(q.size()!=0){
            int pos = q.front();
            q.pop();
            for(const edge& e : g[pos]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[pos]+1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    int dfs(int v,int t,int f){
        if(v==t)return f;
        for(int &i = ite[v];i < (int)g[v].size();i++){
            edge& e = g[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int d = dfs(e.to,t,min(f,e.cap));
                if(d > 0){
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int flow(int s,int t,vector<pair<int,int>>& res){
        int ans = 0;
        while(1){
            if(!bfs(s,t))break;
            ite.assign(n,0);
            int f = dfs(s,t,INF);
            while(1){
                if(f>0){
                    ans += f;
                    f = dfs(s,t,INF);
                }
                else{
                    break;
                }
            }            
        }
        rep(i,n){
            for(edge& e : g[i]){
                if(e.to==s || e.to==t)continue;
                if(e.cap==0){
                    res.push_back({i,e.to});
                }
            }
        }
        return ans;
    }
    int flow(int s,int t){
        int ans = 0;
        while(1){
            if(!bfs(s,t))break;
            ite.assign(n,0);
            int f = dfs(s,t,INF);
            while(1){
                if(f>0){
                    ans += f;
                    f = dfs(s,t,INF);
                }
                else{
                    break;
                }
            }            
        }
        return ans;
    }
};