#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 vizitat(int nod, int *descoperire, )
void comp_biconex(node **graph, int n, int nod, int *ascendent, int *time, int *descoperire, int *low, int *sortare){
(*time)++;
//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, sortare);
       if(low[nod]>low[adiacent->key]){
        low[nod]=low[adiacent->key];
       }
    }
     else{
         if(low[nod]>descoperire[adiacent->key]){
        low[nod]=descoperire[adiacent->key];
       }
     }
     adiacent=adiacent->next;
}
}
void parcurgere_rev(node **graph, int nod, int *vizitat, int *descoperire, int *ascendent, int *low, FILE *pf){
    if(ascendent[nod]){
fprintf(pf, "%d ", nod);
vizitat[nod]=1;
if(descoperire[ascendent[nod]]==low[nod]){
    //vizitat[ascendent[nod]]=1;
    fprintf(pf, "%d\n", ascendent[nod]);
    numc++;
}
else{
    parcurgere_rev(graph, ascendent[nod], vizitat, descoperire, ascendent, low, pf);
}
}
}
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)), *sortare=calloc(n, sizeof(int)) , *vizitat=calloc(n+1, sizeof(int));
   for(int i=1; i<=n; i++) {
       if(!descoperire[i])
        {
            comp_biconex(g, n, i, ascendent, &time ,descoperire, low, sortare);
           // putchar(10);
        }
    }
     pf=fopen("biconex.out", "w");
     fprintf(pf, "             \n");
    for(int i=0; i<n; i++) {
       if(!vizitat[sortare[i]])
        {
           parcurgere_rev(g, sortare[i], vizitat, descoperire, ascendent, low, pf);
        }
    }
    fseek(pf, 0, SEEK_SET);
    fprintf(pf, "%d", numc);
     fclose(pf);
    delete_graph(g, n);
    free(descoperire);
    free(ascendent);
    free(low);
    free(sortare);
    free(vizitat);
    /*
    for(int i=1; i<=n; i++){
        printf("%d ", sort[i]);
    }
    putchar(10);/*
    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;
}