#include <stdio.h>
#include <stdlib.h>
typedef struct typenode{
int key;
struct typenode *next;
} node;

enum {white, gray, black};
int numc;
void print_list(node *first){
while(first){
    printf("%d ", first->key);
    first=first->next;
}
}
void print_list_fisier(node *first, FILE *pf){
while(first){
    fprintf(pf ,"%d ", first->key);
    first=first->next;
}
}
void delete_graph(node **graph, int n){
    int i=0;
for(i=0; i<=n; i++){
    node *tbd=graph[i];
    if(graph[i])
    graph[i]=graph[i]->next;
    while(tbd){
        free(tbd);
    tbd=graph[i];
    if(graph[i])
    graph[i]=graph[i]->next;
    }
}
free(graph);
}
node **citire_graf_fisier(FILE *pf, int *n, int *m){
    int v, w;
    node *aux1, **graph;
fscanf(pf, "%d %d", n, m);
graph=calloc(*n+1, sizeof(node*));
while(fscanf(pf, "%d %d", &v, &w)!=EOF){
    aux1=calloc(1, sizeof(node));
    aux1->key=w;
    aux1->next=graph[v];
    graph[v]=aux1;
}
return graph;
}
node **citire_graf_neorientat_fisier(FILE *pf, int *n, int *m){
    int v, w;
    node *aux1, **graph;
fscanf(pf, "%d %d", n, m);
graph=calloc(*n+1, sizeof(node*));
while(fscanf(pf, "%d %d", &v, &w)!=EOF){
    aux1=calloc(1, sizeof(node));
    aux1->key=w;
    aux1->next=graph[v];
    graph[v]=aux1;

    aux1=calloc(1, sizeof(node));
    aux1->key=v;
    aux1->next=graph[w];
    graph[w]=aux1;
}
return graph;
}
int topological_sort(node **graph, int nod, node** first, int *color){
     //printf("%d ", nod);
color[nod]=gray;
node *adiacent=graph[nod];
while(adiacent){
    if(color[adiacent->key]==white){
        if(!topological_sort(graph, adiacent->key, first, color)) return 0;
    }
    else{
        if(color[adiacent->key]==gray)
       {
           while(*first){
            node *tbd=*first;
            *first=(*first)->next;
            free(tbd);
        }
        return 0;
        }
    }
    adiacent=adiacent->next;
}
color[nod]=black;
node *nou=calloc(1, sizeof(node));
nou->key=nod;
nou->next=*first;
*first=nou;
return 1;
}

int *stack, sf, nrcom;
//int vizitat(int nod, int *descoperire, )
void comp_biconex(node **graph, int n, int nod/*, int *ascendent*/, int *time, int *descoperire, int *low, FILE *pf){
(*time)++;
/*printf("%d ", sf);
printf("%d ", stack[0]);*/
sf++;
stack[sf]=nod;
//printf("%d ", nod);
descoperire[nod]=*time;
//sortare[n-*time]=nod;
low[nod]=descoperire[nod];
int poz, apartenenta=0;
node *adiacent=graph[nod];

while(adiacent){
    if(!descoperire[adiacent->key]){
            //ascendent[adiacent->key]=nod;
       comp_biconex(graph, n, adiacent->key/*, ascendent*/, time, descoperire, low, pf);
       if(low[nod]>low[adiacent->key]){
        low[nod]=low[adiacent->key];
       }
       else{
        if(descoperire[nod]==low[adiacent->key]){
                nrcom++;
            while(stack[sf]!=nod){
                fprintf(pf, "%d ", stack[sf]);
                sf--;
            }
            fprintf(pf, "%d\n", stack[sf]);
        }
       }
    }
     else{
         if(low[nod]>descoperire[adiacent->key]){
        low[nod]=descoperire[adiacent->key];
       }
     }
     adiacent=adiacent->next;
}
//putchar(10);
}


node **g, *graf_sortat;
int n, m, *color, time;
int main()
{
   FILE *pf=fopen("biconex.in", "r");

    g=citire_graf_neorientat_fisier(pf, &n, &m);
    fclose(pf);

    int *descoperire=calloc(n+1, sizeof(int));
    int *ascendent=calloc(n+1, sizeof(int));
    int *low=calloc(n+1, sizeof(int)); stack=calloc(n, sizeof(int));
    pf=fopen("biconex.out", "w");
     fprintf(pf, "             \n");
   for(int i=1; i<=n; i++) {
       if(!descoperire[i])
        {   sf=-1;
            comp_biconex(g, n, i, &time ,descoperire, low, pf);
        }
    }
    fseek(pf, 0, SEEK_SET);
    fprintf(pf, "%d", nrcom);
     fclose(pf);

    delete_graph(g, n);
    free(descoperire);

    free(low);
    free(stack);

   /*
    for(int i=1; i<=n; i++){
        printf("%d ", ascendent[i]);
    }*/
    /*color=calloc(n+1, sizeof(int));
    int i=0;
    for(i=1; i<=n; i++){
        if(!color[i])
            {
                topological_sort(g, i, &graf_sortat,  color);
                //if(!topological_sort(g, i, &graf_sortat,  color)) {printf("nu are sortare topologica"); break;}
               // componente+=3;
               // putchar(10);
            }
    }
    free(color);
   pf=fopen("topsort.out", "w");
    print_list_fisier(graf_sortat, pf);
    //print_list(graf_sortat);
    fclose(pf);
    while(graf_sortat){
            node *tbd=graf_sortat;
            graf_sortat=graf_sortat->next;
            free(tbd);
        }
    delete_graph(g, n);*/

    return 0;
}