#include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<cstring>

 #define mp make_pair

 #define pb push_back

 #define first fi

 #define second se

 #define pw(x) (1ll << (x))

 #define sz(x) ((int)(x).size())

 #define all(x) (x).begin(),(x).end()

 #define rep(i,l,r) for(int i=(l);i<(r);i++)

 #define per(i,r,l) for(int i=(r);i>=(l);i--)

 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)

 #define eps 1e-9

 #define PIE acos(-1)

 #define cl(a,b) memset(a,b,sizeof(a))

 #define fastio ios::sync_with_stdio(false);cin.tie(0);

 #define lson l , mid , ls

 #define rson mid + 1 , r , rs

 #define ls (rt<<1)

 #define rs (ls|1)

 #define INF 0x3f3f3f3f

 #define LINF 0x3f3f3f3f3f3f3f3f

 #define freopen freopen("in.txt","r",stdin);

 #define cfin ifstream cin("in.txt");

 #define lowbit(x) (x&(-x))

 #define sqr(a) a*a

 #define ll long long

 #define ull unsigned long long

 #define vi vector<int>

 #define pii pair<int, int>

 #define dd(x) cout << #x << " = " << (x) << ", "

 #define de(x) cout << #x << " = " << (x) << "\n"

 #define endl "\n"

 using namespace std;

 //**********************************

 struct Edge{

     int from,to,cap,flow;

 }edge;

 void addedge(int from,int to,int cap)

 {

     edge.pb((Edge){from,to,cap,});

     edge.pb((Edge){to,from,,});

     m=sz(edge);

     G[from].pb(m-);G[to].pb(m-);

 }

 struct Dinic{

     int n,m,s,t;

     vector<Edge>edge;

     vi G[maxn];

     int d[maxn];

     int cur[maxn];

     bool bfs()

     {

         cl(vis,);

         queue<int>Q;

         d[s]=;vis[s]=;Q.push(s);

         while(!Q.empty()){

             int x=Q.front();Q.pop();

             rep(i,,sz(G[x])){

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

                     vis[e.to]=;

                     d[e.to]=d[x]+;

                     Q.push(e.to);

                 }

             }

         }

         return vis[t];

     }

     int dfs(int x,int a)

     {

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

         int flow=,f;

         rep(i,cur[x],sz(G[x])){

             cur[x]=i;

             Edge& e=edge[G[x][i]];

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

                 e.flow+=f;

                 edge[G[x][i]^].flow-=f;

                 flow+=f;

                 a-=f;

                 if(a==)break;

             }

         }

         return flow;

     }

     int Maxflow(int s,int t)

     {

         this->s=s;this->t=t;

         int flow=;

         while(bfs()){

             cl(cur,);

             flow+=dfs(s,INF);

         }

         return flow;

     }

 };

 //**********************************

 //**********************************

 int main()

 {

     return ;

 }