#include<bits/stdc++.h>
using namespace std;
#define M 10001
#define inf 100000
int ip=0,head[M],lv[M];
struct E{
    int to,next,cap;
}e[M];
void add(int x,int y,int z){
    e[ip].to=y;e[ip].next=head[x];e[ip].cap=z;head[x]=ip++;
    e[ip].to=x;e[ip].next=head[y];e[ip].cap=0;head[y]=ip++;
}
int s,t;
bool bfs(){
    memset(lv,-1,sizeof(lv));
    queue<int> q;
    q.push(s);
    lv[s]=0;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i=head[t];~i;i=e[i].next){
            if(~lv[e[i].to]&&e[i].cap){
                lv[e[i].to]=lv[t]+1;
                q.push(e[i].to);
            }
        }
    }
    return ~lv[t];
}

int dfs(int u,int f){
    if(u==t||f==0)return f;
    int ret=0;
    for(int i=head[u];~i;i=e[i].next){
        if(lv[e[i].to]==lv[u]+1&&e[i].cap){
            int w=dfs(e[i].to,min(f,e[i].cap));
            e[i].cap-=w;
            e[i^1].cap+=w;
            f-=w;
            ret+=w;
        }
    }
    if(!ret)lv[u]=-1;
    return ret;
}
int dinic(){
    int ans=0;
    while(bfs()){
        ans+=dfs(s,inf);
    }
    return ans;
}

int main(){
    
    return 0;
}