#include <bits/stdc++.h>

 using namespace std;

 const int N (1e5+), M(1e5+);

 int head[N];

 struct Edge{

     /*

     r: residual capacity

     */

     int v, r, nt;

 }E[M];

 int tail;

 void add_edge(int u, int v, int c){

     E[tail]={v, c, head[u]}, head[u]=tail++;

     E[tail]={u, , head[v]}, head[v]=tail++;

 }

 int level[N];

 void bfs(int s){

     memset(level, -, sizeof(level));

     queue<int> que;

     level[s]=;

     que.push(s);

     for(int u; !que.empty(); ){

         u=que.front(), que.pop();

         for(int i=head[u]; ~i; i=E[i].nt){

             int &v=E[i].v;

             if(E[i].r> && level[v]<){

                 level[v]=level[u]+;

                 que.push(v);

             }

         }

     }

 }

 int iter[N];

 int dfs(int u, int t, int f){

     /*

     t: terminal (sink)

     */

     if(u==t) return f;

     //for(int &i=iter[u]; i!=-1; i++){

     for(int &i=iter[u]; i!=-; i=E[i].nt){

         int &v=E[i].v, &r=E[i].r;

         if(r> && level[u]<level[v]){

             int d=dfs(v, t, min(f, r));

             if(d>){

                 r-=d;

                 E[i^].r+=d;

                 return d;

             }

         }

     }

     return ;

 }

 int dinic(int s, int t){

     const int INF=<<;

     for(int flow=;;){

         bfs(s);

         if(level[t]<) return flow;

         memcpy(iter, head, sizeof(iter));

         for(int f; f=dfs(s, t, INF); flow+=f);

     }

 }

 void init(){

     tail=;

     memset(head, -, sizeof(head));

 }