struct Edge{    int x,y,c,ne;}e[M*2];int be[N],all;int d[N],q[N];int stack[N],top;//栈存的是边int cur[N];//当前弧优化
void add(int x, int y, int z)//需保证相反边第一个为偶数{    e[all].x=x; e[all].y=y; e[all].c=z;    e[all].ne=be[x];    be[x]=all++;    e[all].x=y; e[all].y=x; e[all].c=0;    e[all].ne=be[y];    be[y]=all++;}
bool BFS(int s, int t)//化为层次图 使得边数从m降低为n 复杂度随之下降{    memset(d,-1,sizeof(d));    int head=0,tail=0;    q[++tail]=s;    d[s]=0;    while(head!=tail)    {        int u=q[++head];        for(int i=be[u]; i!=-1; i=e[i].ne)        if(e[i].c>0 && d[e[i].y]==-1){            d[e[i].y]=d[u]+1;            q[++tail]=e[i].y;            if(tail==N-1) tail=0;            if(e[i].y==t) return 1;        }    }    return 0;}int Dinic(int s, int t)//防止爆栈 用stack模拟递归{    int ans=0;    while(BFS(s,t))    {        memcpy(cur,be,sizeof(be));        int u=s;        top=0;//dfs开始 清空栈        while(1)        {            if(u==t)            {                int minc=1000000000,mini;                for(int i=0; i<top; i++)                    if(minc>e[stack[i]].c)                    {                        minc=e[stack[i]].c;                        mini=i;//以便之后回到这继续增广                    }                for(int i=0; i<top; i++)                {                    e[stack[i]].c-=minc;                    e[stack[i]^1].c+=minc;//第一个二进制取反 即取相反边                }                ans+=minc;                top=mini;                u=e[stack[mini]].x;            }            for(int i=cur[u]; i!=-1; cur[u]=i=e[cur[u]].ne)                if(e[i].c>0 && d[e[i].y]==d[e[i].x]+1) break;            if(cur[u]!=-1)            {                stack[top++]=cur[u];                u=e[cur[u]].y;            }else            {                if(top==0) break;   //循环结束标志                d[u]=-1;//当前节点不在增广路中 删除                u=e[stack[--top]].x;//回溯            }        }    }    return ans;}

struct Edge{    int x,y,c,ne;}e[M*2];int x,y,z,n,m,s,t;int be[N],all;int d[N],q[N];int stack[N];//模拟递归int gap[N],cur[N];//gap优化+当前弧优化void add(int x, int y, int z)//保证第一个为偶数{    e[all].x=x; e[all].y=y; e[all].c=z;    e[all].ne=be[x];    be[x]=all++;    e[all].x=y; e[all].y=x; e[all].c=0;    e[all].ne=be[y];    be[y]=all++;}void BFS(int s, int t){    memset(d,-1,sizeof(d));    memset(gap,0,sizeof(gap));    gap[0]=1;    int head=0,tail=0;    q[++tail]=t;    d[t]=0;    while(head!=tail)    {        int u=q[++head];        for(int i=be[u]; i!=-1; i=e[i].ne)            if(d[e[i].y]==-1)            {                d[e[i].y]=d[u]+1;                q[++tail]=e[i].y;                gap[d[e[i].y]]++;            }    }}int sap(int s, int t, int n){    int ans=0;    BFS(s,t);    memcpy(cur,be,sizeof(be));    int top=0;    int u=s;    while(d[s]<n)    {        if(u==t)        {            int minc=1000000000,mini;            for(int i=0; i<top; i++)                if(minc>e[stack[i]].c)                {                    minc=e[stack[i]].c;                    mini=i;                }            for(int i=0; i<top; i++)            {                e[stack[i]].c-=minc;                e[stack[i]^1].c+=minc;            }            ans+=minc;            top=mini;            u=e[stack[mini]].x;            continue;        }        for(int i=cur[u]; i!=-1; cur[u]=i=e[i].ne)//当前弧优化            if(e[i].c>0 && d[e[i].y]+1==d[u]) break;        if(cur[u]!=-1)        {            stack[top++]=cur[u];            u=e[cur[u]].y;        }else        {            int mind=n;            for(int i=be[u]; i!=-1; i=e[i].ne)//更新距离标号                if(e[i].c>0 && mind>d[e[i].y])                {                    mind=d[e[i].y];                    cur[u]=i;                }            gap[d[u]]--;            if(!gap[d[u]]) return ans;//gap表示当前距离的点有多少个 一旦==0 说明断层直接退出循环            d[u]=mind+1;            gap[d[u]]++;            if(u!=s) u=e[stack[--top]].x;        }    }    return ans;}void init(){    all=0;    memset(be,-1,sizeof(be));}