Dinicintlevel[NMax];intmkLevel(){for(inti=(level[0]=0)+1;i<N;i++)level[i]=-1;staticintQ[NMax],bot;Q[(bot=1)-1]=0;for(inttop=0;top<bot;top++){intx=Q[top];for(edge*p=E[x];p;p=p->next)if(level[p->e]==-1&&p->f)level[Q[bot++]=p->e]=level[x]+1;}returnlevel[N-1]!=-1;}intextend(inta,intb){intr=0,t;if(a==N-1)returnb;for(edge*p=E[a];p&&r<b;p=p->next)if(p->f&&level[p->e]==level[a]+1){t=p->f;if(t>b-r)t=b-r;t=extend(p->e,t);r+=t;p->f-=t;OPT(p)->f+=t;}if(!r)level[a]=-1;returnr;}intDinic(){intret=0,t;while(mkLevel())while((t=extend(0,1000000000)))ret+=t;returnret;}RelabelToFront#include<cstdio>#include<math.h>#include<ctime>#defineMMax300000#defineNMax20020usingnamespacestd;#defineOPT(_)(epool+(((_)-epool)^1))structedge{inte,f;edge*next;}epool[MMax+MMax],*etop;edge*E[NMax];intN;intRelabelToFront(){staticinth[NMax],e[NMax],pre[NMax],next[NMax];staticedge*cur[NMax];inthead,u;for(inti=1;i<N-1;i++){h[i]=0;e[i]=0;pre[i]=i-1;next[i]=i+1;cur[i]=E[i];}h[0]=N;h[N-1]=0;e[N-1]=e[0]=0;u=head=1;for(edge*p=E[0];p;p=p->next){e[p->e]+=p->f;OPT(p)->f+=p->f;p->f=0;}while(u<N-1){intoh=h[u];while(e[u]){for(;cur[u]&&e[u];cur[u]=cur[u]->next)if(h[cur[u]->e]==h[u]-1&&cur[u]->f){intt=cur[u]->f;if(t>e[u])t=e[u];cur[u]->f-=t;OPT(cur[u])->f+=t;e[u]-=t;e[cur[u]->e]+=t;}if(e[u]){h[u]=N+N;for(edge*p=E[u];p;p=p->next)if(p->f&&h[u]>h[p->e]+1)h[u]=h[p->e]+1;cur[u]=E[u];}}if(h[u]>oh){if(head!=u){if(next[u]<N-1)pre[next[u]]=pre[u];if(pre[u]>0)next[pre[u]]=next[u];next[u]=head;pre[u]=0;pre[head]=u;head=u;}}u=next[u];}returne[N-1];}intlevel[NMax];intmkLevel(){for(inti=(level[0]=0)+1;i<N;i++)level[i]=-1;staticintQ[NMax],bot;Q[(bot=1)-1]=0;for(inttop=0;top<bot;top++){intx=Q[top];for(edge*p=E[x];p;p=p->next)if(level[p->e]==-1&&p->f)level[Q[bot++]=p->e]=level[x]+1;}returnlevel[N-1]!=-1;}intextend(inta,intb){intr=0,t;if(a==N-1)r