Graph contract(Graph &g, int s, int t) {
    Graph contracted(g.n - 1);
    vector<int> label(g.n);
    for (int v = 0; v < g.n; v++) label[v] = v;
    swap(label[t], label[g.n - 1]);
    for (int v = 0; v < g.n; v++) {
        if (v == s || v == t) continue;
        int cap = 0;
        for (int i: g.adj[v]) {
            int w = g.edges[i].v, u = g.edges[i].u;
            if (w == s || w == t) cap += u;
            else if (v < w) contracted.add_edge(label[v], label[w], u);
        }
        if (cap > 0) contracted.add_edge(label[v], label[s], cap);
    }
    return contracted;
}

int mincut(Graph g) {
    int mincap = INF;
    while (g.n > 1) {
        vector<int> weight(g.n, 0);
        vector<bool> in_A(g.n, false);
        int s = -1, t = -1;
        for (int i = 0; i < g.n; i++) {
            int v = -1;
            for (int w = 0; w < g.n; w++) {
                if (in_A[w]) continue;
                if (v == -1 || weight[w] > weight[v]) v = w;
            }
            s = t;
            t = v;
            for (int j: g.adj[v]) {
                int w = g.edges[j].v, u = g.edges[j].u;
                if (!in_A[w]) weight[w] += u;
            }
            in_A[v] = true;
        }
        mincap = min(mincap, weight[t]);
        g = contract(g, s, t);
    }
    return mincap;
}