#include<stdio.h>
#define infile "biconex.in"
#define outfile "biconex.out"
#define nmax (100*1000+1)
#define mmax (400*1000+1)
#define start 1 //nodul de start din care vom face aprcurgerea
int save[mmax], nrpos, nrcom; //vectorul in care salvam componentele biconexe,, variabila cu pozitiile ocupate de componente, si variabila in care salvam numarul lor
struct lista
{
int n,p; //nodul, respectiv pozitia din lista a lu frasu
} l[mmax];
struct nod
{
int p; //pozitia din lista a ultimului fiu
int nr; //numarul de ordine din parcurgerea dfs
int nrt; //numarul minim de ordine al unui stramos din parcurgerea dfs (!tata)
} p[nmax];
struct stiva
{
int t,f; //muchia de la tata la fiu :P
} s[mmax];
int nro; //numarul de ordine al nodurilor in parcurgere
int st; //numarul de elemente din stiva
int n; //numarul de noduri
//adaugam arcul (x,y)
void add(struct lista l[mmax], struct nod p[nmax], int m, int x, int y)
{
l[m].n=y; l[m].p=p[x].p; p[x].p=m;
}
void citire(struct lista l[mmax], struct nod p[nmax], int *n)
{
int m,x,y,i,j;
scanf("%d %d\n",n,&m);
for(j=0,i=1;i<=m;i++) //citim fiecare muchie :P
{
scanf("%d %d\n",&x,&y);
add(l,p,++j,x,y);
add(l,p,++j,y,x);
}
}
void initializare(struct lista l[mmax], struct nod p[nmax], struct stiva s[mmax], int *st, int n)
{
int i;
for(i=1;i<=n;i++) p[i].nr=p[i].nrt=-1; //initial nu au fost atinse punctele in parcurgere :P
*st=0; s[0].t=-1; s[0].f=start; //adaugam o muchie fictiva catre nodul de start :P
}
//salveaza componenta in vectorul global save[]
void salveaza_componenta(struct stiva s[mmax], int *st, int u, int x)
{
struct stiva pct;
nrcom++; //am gasit o componenta biconexa
do { pct=s[*st]; *st-=1; save[++nrpos]=pct.f; }
while(pct.t!=u || pct.f!=x );
save[++nrpos]=0; //sa stim ca am marcat o componenta biconexa
}
//parcurgere in inaltime facuta a.i. sa afla componentele biconexe (din nodul u, cu tatal ut)
void dfs(struct lista l[mmax], struct nod p[nmax], struct stiva s[mmax], int *st, int u, int ut)
{
p[u].nr=p[u].nrt=++nro; //punem numarul de ordine....
int x,ul=p[u].p; //aici vom avea pozitia din lista a fiilor lui u
while(ul) //cat timp u mai are copii
{
x=l[ul].n; //copilul lui u
if(x!=ut)// && p[x].nr<p[u].nr) //daca copilul nu e defapt tatal, si daca copilul este defapt un stramos sau nu a mai fost vizitat /////////////////////////////////////////////////////////////////////////////
{ *st+=1; s[*st].t=u; s[*st].f=x; } //adaugam muchia in stiva
if(p[x].nr==-1) //acest nod nu a mai fost vizitat...
{
dfs(l,p,s,st,x,u); //parcurgem nodul :P
if(p[x].nrt<p[u].nrt) p[u].nrt=p[x].nrt; //daca copilul lui u poate ajunge la un stramos mai invarsta (cu numarul de ordine cat mai mic)
if(p[x].nrt>=p[u].nr) //u este nod de articulatie
salveaza_componenta(s,st,u,x); //salvam componenta biconexa, si o scoatem din stiva:P
}
else if(x!=ut) //daca a mai fost vizitat, si daca nu este tatal nodului
if(p[u].nrt>p[x].nr) p[u].nrt=p[x].nr; //fiind deja vizitat, si nefiind tata, inseamna ca este stramos....daca este cel mai inalt nod ce poate fi atins (nr ordine mic), salvam asta :P
ul=l[ul].p; //trecem la un alt copil al nodului u
}
}
void afisare(int save[mmax], int nrpos, int nrcom)
{
int i;
printf("%d\n",nrcom);
for(i=1;i<=nrpos;i++)
if(!save[i]) printf("\n"); //am terminat de afisat o componenta biconexa
else printf("%d ",save[i]);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
citire(l,p,&n); //citim datele din fisier
initializare(l,p,s,&st,n); //facem initializarea nodurilor si a stivei
dfs(l,p,s,&st,start,-1); //parcurgem graful din nodul start...pt a afla numarul de componente biconexe
afisare(save,nrpos,nrcom);
fclose(stdin);
fclose(stdout);
return 0;
}