//Dinic

struct Edge{

    int from,to,cap,flow;

    Edge(){

    }

    Edge(int a,int b,int c,int d){

        from=a;

        to=b;

        cap=c;

        flow=d;

    }

}edges[maxm*];

int n,m,s,t,sz;

vector<int> ve[maxn];

int dis[maxn],cur[maxn];

bool vis[maxn];

int l,r;

void addEdge(int a,int b,int c)

{

    edges[sz++]=Edge(a,b,c,);

    edges[sz++]=Edge(b,a,,);

    ve[a].push_back(sz-);

    ve[b].push_back(sz-);

}

bool BFS(){

    memset(vis,,sizeof(vis));

    queue<int> qu;

    qu.push(s);

    dis[s]=;

    vis[s]=;

    while(qu.size()){

        int u=qu.front();qu.pop();

        for(int i=;i<ve[u].size();i++){

            Edge& e=edges[ve[u][i]];

            if(!vis[e.to] && e.flow<e.cap){

                vis[e.to]=;

                qu.push(e.to);

                dis[e.to]=dis[u]+;

            }

        }

    }

    return vis[t];

}

int DFS(int x,int a)

{

    if(x==t || a==)return a;

    int flow=,f;

    for(int& i=cur[x];i<ve[x].size();i++){

        Edge e=edges[ve[x][i]];

        if(dis[x]+==dis[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>){

            flow+=f;

            a-=f;

            edges[ve[x][i]].flow+=f;

            edges[ve[x][i]^].flow-=f;

            if(a==)break;

        }

    }

    return flow;

}

int dinic()

{

    int flow=;

    while(BFS()){

        memset(cur,,sizeof(cur));

        flow += DFS(s,);

    }

    return flow;

}