#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100005;

int n, m, tot;
vector<int> g[N];          // 原图邻接表
vector<int> adj[N * 2];      // 圆方树邻接表 (开 2N)

int dfn[N], low[N], timer;
int stk[N], top;

inline void add_tree_edge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;

    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                int sq = ++tot;
                add_tree_edge(u, sq);
                do{
                    add_tree_edge(stk[top],sq);
                }while(stk[top--]!=v);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void build_bct() {
    tot = n;
    timer = top = 0;
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
            if (top > 0) --top; // 弹出孤立根节点
        }
    }
}