struct Edge {

    int lst, from, to, cap, flow;

    Edge () { }

    Edge (int  ll, int ff, int tt, int cc, int fff) : lst(ll), from(ff), to(tt), cap(cc), flow(fff) { }

};

const int maxn = ;

const int  inf = 0x3f3f3f3f;

class Edmonds_karp {

public:

     Edge edge[maxn*];

     int head[maxn];

     int cn, cm;

     int csz;

     int path[maxn];

     int deta[maxn];

    void init(int n, int m) {

        cn = n; cm = m;

        memset(head, , sizeof(head));

        csz = ;  // 注意 这儿应该是偶数开始  因为 奇数^1等价于减1 偶数^1等价于加一.

                  // 因为我前向星是以0为结尾的 所以我必须从2开始.

    }

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

         edge[csz] = Edge(head[u], u, v, c, );

         head[u]   = csz++;

         edge[csz] = Edge(head[v], v, u, , );  // 反向边,记得容量为0, 但是有些情况是可以修改的. 例如在建无向图的时候.

         head[v]   = csz++;

     }

     int maxflow(int st, int ed) {

         int res = ;

         int i, u, v, cap, flow;

         while (true) {

             // 找增广路

             memset(deta, , sizeof(deta));

            queue<int> q;

            q.push(st);

            deta[st] = inf;

            while (!q.empty()) {

                u = q.front(); q.pop();

                for (i=head[u]; i; i=edge[i].lst) {

                    v = edge[i].to; cap = edge[i].cap; flow = edge[i].flow;

                    if (!deta[v] && cap > flow) {  // 该点未被增广, 同时可流

                        deta[v] = min(deta[u], cap - flow); // 限流

                        path[v] = i; // 记录路径

                        q.push(v);

                    }

                }

                if (deta[ed]) break; // 找到一条增广路了.

            }

             if (!deta[ed])    break; // 如果找不到增广路就说明最大流了,结束.

             for (i=path[ed]; i!=path[st]; i=path[edge[i].from]) {   // 更新残量图

                   edge[i].flow += deta[ed];

                 edge[i^].flow -= deta[ed];

            }

             res += deta[ed];

        }

         return res;

     }

}Ek;

struct Edge {

    int from, to, cap, flow;

    Edge (int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) { }

};

struct EdmondsKarp {

    int n, m;

    vector<Edge> edges;

    vector<int>  G[maxn];

    int a[maxn];

    int p[maxn];

　　　　void init(int n) {
　　　　　　this->n = n;
　　　　　　for (int i=0; i<=n; ++i) G[i].clear(), edges.clear();
　　　　}

void add(int u, int v , int val) {

        edges.push_back(Edge(u, v, val, ));

        edges.push_back(Edge(v, u, , ));

        m = edges.size();

        G[u].push_back(m-);

        G[v].push_back(m-);

    }

    int Maxflow(int s, int t) {

        int flow = ;

        while () {

            memset(a, , sizeof(a));

            queue<int> Q;

            Q.push(s);

            a[s] = inf;

            while (!Q.empty()) {

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

                for (int i=; i<G[x].size(); ++i) {

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

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

                        p[e.to] = G[x][i];

                        a[e.to] = min(a[x], e.cap - e.flow);

                        Q.push(e.to);

                    }

                }

                if (a[t]) break;

            }

            if (!a[t]) break;

            for (int u = t; u!=s; u =edges[p[u]].from) {

                edges[p[u]].flow += a[t];

                edges[p[u]^].flow -= a[t];

            }

            flow += a[t];

        }

        return flow;

    }

}Ek;