#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_set>

using namespace std;

class Graf{
private:
    int m_nrNoduri;
    vector<vector<int>> m_listAdiacenta;
    vector<int> viz;
    vector<int> arrivalTime;
    vector<int> lowLinkValue;
    vector<unordered_set<int>> componenteBiconexe;
    stack<pair<int,int>> StivaMuchiiComponentaBiconexaCurenta;
public:
    void citireGrafNeorientat(char *fisier);
    void citireGrafOrientat(char *fisier);
    void createViz(int val);
    void initArrivalTime();
    void initLowLinkValue();
    void initViz();

    void BFS(int nod);
    void DFS(int nod);

    void afisDrumuriMinime(vector<int> drumurileMinime);
    void afisNumarComponenteConexe(char *fisier);
    int numaraComponenteConexe();
    void afisComponenteBiconexe();
    /*void afisComponenteTareConexe();*/

    int citireBFSINfoarena();
    void DFSBiconexe(int nodCurent, int precedent, int pas);
};

void Graf::citireGrafNeorientat(char *fisier){
    ifstream f(fisier);
    vector<int> aux;
    int nrMuchii;

    f>>this->m_nrNoduri;
    this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);

    f>>nrMuchii;

    for(int i=0; i<nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->m_listAdiacenta[x].push_back(y);
        this->m_listAdiacenta[y].push_back(x);
    }
}


void Graf::citireGrafOrientat(char *fisier){
    ifstream f(fisier);
    vector<int> aux;
    int nrMuchii;

    f>>this->m_nrNoduri;
    this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);

    f>>nrMuchii;

    for(int i=0; i<nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->m_listAdiacenta[x].push_back(y);
    }
}

int Graf::citireBFSINfoarena(){
    ifstream f("bfs.in");

    vector<int> aux;
    int nrMuchii, nodSursa;

    f>>this->m_nrNoduri;
    this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);

    f>>nrMuchii;

    f>>nodSursa;

    for(int i=0; i<nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->m_listAdiacenta[x].push_back(y);
    }
    return nodSursa;
}

void Graf::createViz(int val){
    this->viz.assign(this->m_nrNoduri+1, val);
}

void Graf::initArrivalTime(){
    this->arrivalTime.assign(this->m_nrNoduri+1, -1);
}

void Graf::initViz(){
    this->viz.assign(this->m_nrNoduri+1, 0);
}

void Graf::initLowLinkValue(){
    this->lowLinkValue.resize(this->m_nrNoduri+1);
}

void Graf::BFS(int nod){
        //initializam vectorul de distante minime
    vector<int> distante;
    distante.assign(100001, 0);
    int curent;
        //in coada vom pune nodurile pe massura ce le parcurgem
    queue<int> coada;
        //initial toate nodurile sunt nevizitate, asaa ca initializam viz[orice nod] = 0
    this->createViz(0);
        //adaugam nodul sursa in coada si il marcam ca si vizitat
    coada.push(nod);
    this->viz[nod] = 1;
        //actualizam vectorul de distante pentru nodul curent cu distanta pana la el, adica 1
    distante[nod] = distante[nod] + 1;

        //facem BFS-ul
    while(!coada.empty()){
        curent = coada.front();
            //parcurgem vecinii nodului curent si pe fiecare vecin nevizitat il adaugam in coada, ii actualizam distanta pana la el si il marcam ca si vizitat
        for(int i=0; i < this->m_listAdiacenta[curent].size(); i++){
            if(this->viz[this->m_listAdiacenta[curent][i]] == 0){
                coada.push(this->m_listAdiacenta[curent][i]);
                distante[coada.back()] = distante[curent]+1;
                this->viz[this->m_listAdiacenta[curent][i]] = 1;
            }
        }
            //am terminat cu nodul curent, il scoatem din coada
        coada.pop();
    }

    this->afisDrumuriMinime(distante);
}

void Graf::afisDrumuriMinime(vector<int> drumuriMinime){
    ofstream g("bfs.out");
    for(int i=1; i <= this->m_nrNoduri; i++){
        g<<drumuriMinime[i] - 1<<" ";
    }
}

void Graf::DFS(int nod){
        //marcam nodul curent ca vizitat
    this->viz[nod] = 1;
        //parcurgem vecinii si pentru fiecare vecin nevizitat aplicam recursiv DFS
    for(int i=0; i<this->m_listAdiacenta[nod].size(); i++){
        if(this->viz[this->m_listAdiacenta[nod][i]] == 0){
            DFS(this->m_listAdiacenta[nod][i]);
        }
    }
}

int Graf::numaraComponenteConexe(){
        //numarul componentelor conexe il vom tine in nr
    int nr = 0;
        //initial toate nodurile sunt nevizitate
    this->createViz(0);

        //pentru fiecare nod nevizitat parcurgem din copil in copil prin DFS; de fiecare data cand dam de un nod nevizitat inseamna ca avem o noua componenta conexa
    for(int nod = 1; nod <= this->m_nrNoduri; nod++){
        if(this->viz[nod] == 0){
            nr++;
            DFS(nod);
        }
    }

    return nr;
}

void Graf::afisNumarComponenteConexe(char *fisier){
    ofstream g(fisier);

    g<<this->numaraComponenteConexe();
}

void Graf::afisComponenteBiconexe(){
    //ofstream g(fisier);
    ofstream g("biconex.out");

    /*this->initViz();
    this->initArrivalTime();
    this->initLowLinkValue();*/

    this->viz.assign(this->m_nrNoduri+1, 0);
    this->arrivalTime.assign(this->m_nrNoduri+1,-1);
    this->lowLinkValue.reserve(this->m_nrNoduri+1);

    DFSBiconexe(1,0,0);

    int marime = this->componenteBiconexe.size();
    unordered_set<int>::iterator it;
    g<<marime<<"\n";
    for(int i=0; i<marime; i++){
        for(it = componenteBiconexe[i].begin(); it != componenteBiconexe[i].end(); it++){
            g<<*it<<" ";
        }
        g<<"\n";
    }
}

void Graf::DFSBiconexe(int nodCurent, int precedent, int pas){
    //marcam ca vizitat nodul curent
    this->arrivalTime[nodCurent] = pas;

    //momentan nivelul minim de intoarcere e nivelul curent, adica pasul
    this->lowLinkValue[nodCurent] = pas;

    //parcurgem vecinii nodului curent
    for(int i=0; i<this->m_listAdiacenta[nodCurent].size(); i++){
        int vecinCurent = this->m_listAdiacenta[nodCurent][i];
        if(vecinCurent != precedent){
            //verificam pe ce fel de muchie suntem
            //daca vecinul curent a mai fost vizitat inseamna ca am dat de o muchie de intoarcere, altfel suntem pe o muchie in jos
            if(this->arrivalTime[vecinCurent] == -1){
                //am dat de o noua muchie din componenta biconexa curenta, asa ca o adaugam in stiva
                StivaMuchiiComponentaBiconexaCurenta.push(make_pair(nodCurent, vecinCurent));
                //apelam DFS pentru vecinul curent
                DFSBiconexe(vecinCurent, nodCurent, pas + 1);
                //verificam daca atunci cand ne am dus mai departe in graf
                // am dat de o muchie de intoarcere care ne duce mai sus decat ne ducea nodul acesta inainte
                if(this->lowLinkValue[nodCurent] > this->lowLinkValue[vecinCurent]){
                    this->lowLinkValue[nodCurent] = this->lowLinkValue[vecinCurent];
                }
                //verificam daca am ajuns la finalul componentei biconexe
                if(this->lowLinkValue[vecinCurent] >= this->arrivalTime[nodCurent]){
                    //trebuie sa adaugam noua componenta biconexa in vectorul de componenete biconexe
                    //si sa golim stiva cu muchiile componentei biconexe curente
                    unordered_set<int> aux;
                    int aux1, aux2;
                    do{
                        aux1 = this->StivaMuchiiComponentaBiconexaCurenta.top().first;
                        aux2 = this->StivaMuchiiComponentaBiconexaCurenta.top().second;
                        aux.insert(aux1);
                        aux.insert(aux2);
                        this->StivaMuchiiComponentaBiconexaCurenta.pop();
                    } while (aux1 != nodCurent || aux2 != vecinCurent);
                    this->componenteBiconexe.push_back(aux);
                }
            }else{
                //avem o muchie de intoarcere, trebuie sa verificam daca nu cumva duce mai sus
                if(this->lowLinkValue[nodCurent] > this->arrivalTime[vecinCurent]){
                    this->lowLinkValue[nodCurent] = this->arrivalTime[vecinCurent];
                }
            }
        }
    }
}

int main()
{
        /*BFS INFOARENA*/
    /*int nodPornire;
    Graf g;

    nodPornire = g.citireBFSINfoarena();

    g.BFS(nodPornire);*/

        /*DFS INFOARENA*/

    /*Graf g;

    g.citireGrafNeorientat("dfs.in");

    g.afisNumarComponenteConexe("dfs.out");*/

        /*COMPONENTE BICONEXE INFOARENA*/
    Graf g;

    g.citireGrafNeorientat("biconex.in");

    g.afisComponenteBiconexe();
    return 0;
}