BridgeTree

int t,d[MAX],l[MAX];vi v[MAX],edge[MAX];set<pii>bridges;int visited[MAX],cycle[MAX],n,vis[MAX];
void dfs(int s,int p = -1){

    d[s] = l[s] = ++t;
    vis[s] = 1;
    for(auto it : v[s]){
        if(it==p)continue;
        if(vis[it]){

            l[s] = min(l[s],d[it]);
        }
        else {

            dfs(it,s);
            if(d[s]<l[it]){
                int x = min(it,s);
                int y = max(it,s);
                bridges.insert(pii(x,y));
            }
            l[s] = min(l[s],l[it]);
        }
    }
}

void extract_bc(int s,int root)
{
    if(visited[s])return ;
    visited[s] = 1;
    cycle[s] = root;
    for(auto it : v[s]){
        int x = min(it,s);
        int y = max(it,s);
        if(bridges.find(pii(x,y))==bridges.end()){
            extract_bc(it,root);
        }
    }

}

void make_BridgeTree()
{
    for(int i = 1;i<=n;i++)if(!vis[i])dfs(i);
    for(int i = 1;i<=n;i++){
        if(!visited[i])extract_bc(i,i);
    }
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<v[i].size();j++){
            int x = v[i][j];
            if(cycle[i]!=cycle[x]){
                ///cout<<cycle[i]<<" "<<cycle[x]<<" "<<i<<" "<<x<<endl;
                edge[cycle[i]].pb(cycle[x]);
            }
        }
    }

}