#include<bits/stdc++.h>

using namespace std;

const int N=100000,M=200000;

//所有Tarjan都要：

// dfn[N],low[N],cnt=1,st,scc,zhan[N],top,前向星,vector<int>SCC[N]

//强连通 ,belong[N],inq[N]

//割边，边双 bridge[N], belong[N]

//点双，割点 cut[N],root

int dfn[N],low[N],cnt=1,zhan[N],top,st,belong[N],scc,head[N],root,n;

bool bridge[M],inq[N],cut[N];

vector <int>SCC[N];

struct bian

{

    int nxt,to;

}b[M];

void add(int from,int to)

{

    b[++cnt].nxt=head[from];

    b[cnt].to=to;

    head[from]=cnt;

}

void Tarjan1(int cur)//强连通

{

    dfn[cur]=low[cur]=++st;

    zhan[++top]=cur;inq[cur]=true;

    int i=head[cur],v;

    while(i!=0)

    {

        v=b[i].to;

        if(dfn[v]==0)

        {

            Tarjan1(v);

            low[cur]=min(low[cur],low[v]);

        }

        else

        {

            if(inq[v]==true)

            {

                low[cur]=min(low[cur],dfn[v]);

            }

        }

        i=b[i].nxt;

    }

    if(low[cur]==dfn[cur])

    {

        scc++;

        int ding;

        do

        {

            ding=zhan[top];

            inq[ding]=false;

            zhan[top--]=0;

            belong[ding]=scc;

            SCC[scc].push_back(ding);

        }while(ding!=cur);

    }

}

void Tarjan2(int cur,int pre)//割边，边双

{

    dfn[cur]=low[cur]=++st;

    zhan[++top]=cur;

    int i=head[cur],v;

    while(i!=0)

    {

        v=b[i].to;

        if(i!=pre)

        {

            if(dfn[v]==0)

            {

                Tarjan2(v,i^1);

                low[cur]=min(low[cur],low[v]);

                if(low[v]>dfn[cur])

                {

                    bridge[i]=bridge[i^1]=true;

                    scc++;

                    int ding;

                    do

                    {

                        ding=zhan[top];

                        zhan[top--]=0;

                        belong[ding]=scc;

                        SCC[scc].push_back(ding);

                    }while(ding!=v);

                }

            }

            else

                low[cur]=min(low[cur],dfn[v]);

        }

        i=b[i].nxt;

    }

}

void Tarjan3(int cur)

{

    dfn[cur]=low[cur]=++st;

    zhan[++top]=cur;

    int i=head[cur],v,child=0;

    while(i!=0)

    {

        v=b[i].to;

        if(dfn[v]==0)

        {

            child++;

            Tarjan3(v);

            low[cur]=min(low[cur],low[v]);

            if(low[v]>=dfn[cur])

            {

                if(root!=cur)

                    cut[cur]=true;

                scc++;

                int ding;

                do

                {

                    ding=zhan[top];

                    zhan[top--]=0;

                    SCC[scc].push_back(ding);

                }while(ding!=v);

                SCC[scc].push_back(cur);

            }

        }

        else

            low[cur]=min(low[cur],dfn[v]);

        i=b[i].nxt;

    }

    if(cur==root&&child>=2)

    {

        cut[cur]=true;

    }

}

int main()

{

    for(int i=1;i<=n;i++)

    {

        if(dfn[i]==0)

            Tarjan1(i);

        if(dfn[i]==0)

        {

            Tarjan2(i,0);

            int ding;

            while(top>0)

            {

                ding=zhan[top];

                zhan[top--]=0;

                SCC[scc].push_back(ding);

            }

        }

        if(dfn[i]==0)

            root=i,Tarjan3(i);

    }

    return 0;

}