struct edge {
    int tot, flag, hed[N], nxt[M], to[M];
    edge () { tot = 2; }
    void link(int u, int v) {
        nxt[tot] = hed[u], to[tot] = v, hed[u] = tot++;
        nxt[tot] = hed[v], to[tot] = u, hed[v] = tot++;
    }
} G1, G2;

void tarjan(int u, int father) {
    ++base, dfn[u] = low[u] = ++tim, ins[u] = 1, stk[++top] = u;
    for (int i = G1.hed[u], v = G1.to[i]; i; i = G1.nxt[i], v = G1.to[i])
        if (v != father) {
            if (!dfn[v]) {
                tarjan(v, u), low[u] = std::min(low[u], low[v]);
                if (low[v] >= dfn[u]) {
                    G2.link(u, ++tot), ++val[tot]; int x;
                    do {
                        x = stk[top--], ins[x] = 0;
                        G2.link(x, tot), ++val[tot];
                    } while (x != v);
                }
            } else if (ins[v]) low[u] = std::min(low[u], dfn[v]);
        }
}