const int N=1e5+5,inf=1e9;
vector<int> a[N];
stack<int> stk;
bool vis[N],instk[N];
int dfn[N],low[N],col[N],w[N]; // co:染色结果，w:点权
vector<int> sz; // sz:第i个颜色的点数
int n,m,dcnt;//
void dfs(int x){ // Tarjan求强联通分量
    vis[x]=instk[x]=1; stk.push(x);
    dfn[x]=low[x]=++dcnt;
    for(auto p:a[x]){
        if(!vis[p])dfs(p);
        if(instk[p])low[x]=min(low[x],low[p]);
    }
    if(low[x]==dfn[x]){
        int t; sz.push_back(0); // 记录
        do{
            t=stk.top();
            stk.pop();
            instk[t]=0;
            sz.back()+=w[t]; // 记录
            col[t]=sz.size(); // 染色
        }while(t!=x);
    }
}
void getscc(){
    fill(vis,vis+n,0);
    sz.clear();
    for(int i=1;i<=n;i++) if(!vis[i])dfs(i);
}
struct pii{
    int u,v;
};
void shrink(){ // 缩点，在a里重构
    vector<pii> tmp;
    getscc();
    for(int i=1;i<=n;i++) {
        for (auto j: a[i]) if (col[i] != col[j]) {
                pii u = {col[i], col[j]};
                tmp.push_back(u);
            }
    }
    n=sz.size();
    for(int i=1;i<=n;i++){
        a[i].clear();
        w[i]=sz[i];
    }
    for(auto i:tmp){
        a[i.u].push_back(i.v);
    }
}

struct FLOW{
    struct edge{int to,w,nxt;};
    vector<edge> a; int head[N],cur[N];
    int n,s,t;
    queue<int> q; bool inque[N];
    int dep[N];
    void ae(int x,int y,int w){ // add edge
        //cout<<"ae:"<<x<<" "<<y<<" "<<w<<endl;
        a.push_back({y,w,head[x]});
        head[x]=a.size()-1;
    }
    bool bfs(){ // get dep[]
        fill(dep,dep+n,inf); dep[s]=0;
        copy(head,head+n,cur);
        q=queue<int>(); q.push(s);
        while(!q.empty()){
            int x=q.front(); q.pop(); inque[x]=0;
            for(int i=head[x];i!=-1;i=a[i].nxt){
                int p=a[i].to;
                if(dep[p]>dep[x]+1 && a[i].w){
                    dep[p]=dep[x]+1;
                    if(inque[p]==0){
                        inque[p]=1;
                        q.push(p);
                    }
                }
            }
        }
        return dep[t]!=inf;
    }
    int dfs(int x,int flow){ // extend
        int now,ans=0;
        if(x==t)return flow;
        for(int &i=cur[x];i!=-1;i=a[i].nxt){
            int p=a[i].to;
            if(a[i].w && dep[p]==dep[x]+1)
                if((now=dfs(p,min(flow,a[i].w)))){
                    a[i].w-=now;
                    a[i^1].w+=now;
                    ans+=now,flow-=now;
                    if(flow==0)break;
                }
        }
        return ans;
    }
    bool is[N];
    void init(int _n){
        n=_n+1; a.clear();
        fill(head,head+n,-1);
        fill(inque,inque+n,0);
        fill(is,is+n,0);
    }
    int solve(int _s,int _t,int _n){ // return max flow
        s=_s,t=_t;
        int ans=0;
        while(bfs()) ans+=dfs(s,inf);
        for(int e=head[s];e>=0;e=a[e].nxt) if(a[e^1].w) is[a[e].to]=1;
        for(int e=head[t];e>=0;e=a[e].nxt) if(a[e].w){
            int v=a[e].to,u=v;
            while(1){
                if(u>=1 && u<=_n && is[u]){
                    is[u]=0;
                    break;
                }
                int w=0,tmp=0;
                for(int i=head[u];i>=0;i=a[i].nxt) if(i&1 && a[i].w){
                    w=a[i].to;
                    tmp=i;
                    break;
                }
                if(!w) break;
                a[tmp].w--;
                u=w;
            }
            //cout<<u<<" "<<v-_n<<endl;
           // fa[find(u)]=find(v-_n);
        }
        return ans;
    }
}flow;
void add(int x,int y,int w){flow.ae(x,y,w),flow.ae(y,x,0);}