const int maxn = 10110;
const int maxm = 50000;
const int inf = 0x3f3f3f3f;
int n,m ,tol;
int head[maxn];
struct Edge
{
    int to,cap,flow,nex;//加cap通用性更好
    Edge(int to,int cap,int flow,int nex): to(to),cap(cap),flow(flow),nex(nex) {}
    Edge() {}
} edge[maxm];
int dis[maxn];
void init()
{
memset(head,-1,sizeof head);
    tol =0;
}

void addedge(int u,int v,int cap,int rw=0)//单向图3参数，双向图4参数
{
    edge[tol]=Edge(v,cap,0,head[u]);
    head[u]=tol++;
    edge[tol]=Edge(u,rw,0,head[v]);
    head[v]=tol++;
}

bool bfs(int s,int t)
{
    memset(dis,-1,sizeof dis);
    dis[s]=0;
    queue<int> que;
    que.push(s);
    while (!que.empty())
    {
        int u=que.front();que.pop();
        for (int i=head[u];~i;i=edge[i].nex)
        {
            int v=edge[i].to;
            if (dis[v]==-1 && edge[i].cap>edge[i].flow)
            {
                dis[v]=dis[u]+1;
                if (v==t) return true;
                que.push(v);
            }
        }
    }
    return false;
}

int dfs(int x,int t,int cap)
{
    if (x==t) return cap;
    int flow=0,f;
    for (int i=head[x];~i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if (dis[v]==dis[x]+1 && edge[i].cap>edge[i].flow)
        {
            f=dfs(v,t,min(cap-flow,edge[i].cap-edge[i].flow));
            edge[i].flow +=  f;
            edge[i^1].flow -= f;
            flow +=f;
            if (flow == cap) break;
        }
    }
    if (!flow) dis[x]=-1;//加速
    return flow;
}

int dicnic(int s,int t)//起点和终点标号
{
    int flow=0,f;
    while (bfs(s,t))
        while ((f=dfs(s,t,inf))>0)
            flow += f;
    return flow;
}