#include <iostream>
#include<string.h>
#include<bits/stdc++.h>


using namespace std;

ofstream fout("biconex.out");
class Graf
{
private:
    int nr_noduri;
public:
    //constructori
    Graf();
    Graf(int nr_noduri);
    //operatorii de copiere
    Graf(const Graf& g);
    Graf& operator=(const Graf& g);
    //functiile de cititre si afisare
    friend ifstream& operator>>(ifstream& in,Graf& g);
    //destructorul
    ~Graf();
    //functie virtuala pura
    virtual void scrie_tip_graf()=0;
    virtual int begin_dfs()=0;
    virtual void bfs(int nod_start)=0;
    //setteri si getteri
    int get_nr_noduri();

    //citire si afisare virtuala
    virtual ifstream& citire_graf_virtuala_fisier(ifstream& in);




};

int Graf::get_nr_noduri()
{
    return this->nr_noduri;
}
Graf::Graf()
{
    this -> nr_noduri = 0;
}

Graf::Graf(int nr_noduri)
{
    this -> nr_noduri = nr_noduri;
}

Graf::Graf(const Graf& g)
{
    this -> nr_noduri = g.nr_noduri;
}

Graf& Graf::operator=(const Graf& g)
{
    if(this != &g)
    {
        this -> nr_noduri = g.nr_noduri;
    }
    return *this;
}
ifstream& Graf::citire_graf_virtuala_fisier(ifstream& in)
{
    in>>this -> nr_noduri;
    return in;
}
ifstream& operator>>(ifstream& in,Graf& g)
{
    return g.citire_graf_virtuala_fisier(in);
}
Graf::~Graf(){};


class Graf_Neorientat:public Graf
{
private:
    int numar_muchii;
    unordered_map<int,vector<int>>lista_adiacenta;
public:
    //constructori
    Graf_Neorientat();
    Graf_Neorientat(int nr_noduri,int numar_muchii,unordered_map <int,vector<int>> lista_adiacenta);
    //operatorii de copiere
    Graf_Neorientat(const Graf_Neorientat& g);
    Graf_Neorientat& operator=(const Graf_Neorientat& g);
    //functiile de cititre si afisare
    friend ifstream& operator>>(ifstream& in,Graf_Neorientat& g);
    //destructorul
    ~Graf_Neorientat();
    //functii
    int begin_biconex();
    virtual void scrie_tip_graf();
    virtual int begin_dfs();
    void dfs(int nod, int viz[]);
    void dfs_biconex(int nod_start,int viz[],int lista_intoarcere[],int lista_nivel[],int nivel,int mat[],stack<pair<int,int>> &stiva_muchii,unordered_map<int,vector<int>> &lista_fii);
    void dfs_biconex_stiva(int nod_start,int viz[],int lista_intoarcere[],int lista_nivel[],stack<pair<int,int>> &stiva_muchii,set<int,less<int>> &componenta_biconexa,int lista_noduri_critice[]);
    virtual void bfs(int nod_start);
    //setteri si getteriofstream fout("biconex.out");
    int get_nr_muchii();
    unordered_map<int,vector<int>> get_lista_adiacenta();


    //citire si afisare virtuala
    virtual ifstream& citire_graf_virtuala_fisier(ifstream& in);


};
void Graf_Neorientat::dfs_biconex_stiva(int nod,int viz[],int lista_intoarcere[],int lista_nivel[],stack<pair<int,int>> &stiva_muchii,set<int,less<int>> &componenta_biconexa,int lista_noduri_critice[])
{
    viz[nod] = 1;
    int nr_noduri2 = Graf_Neorientat::get_nr_noduri();

    if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
    {
        for(int i=1;i<=lista_adiacenta[nod].size();i++)
            if(viz[lista_adiacenta[nod][i-1]] == 0)
        {
            pair<int,int> muchie_curenta;
            muchie_curenta.first = nod;
            muchie_curenta.second = lista_adiacenta[nod][i-1];
            stiva_muchii.push(muchie_curenta);
            dfs_biconex_stiva(lista_adiacenta[nod][i-1],viz,lista_intoarcere,lista_nivel,stiva_muchii,componenta_biconexa,lista_noduri_critice);
            while((lista_noduri_critice[stiva_muchii.top().first]!=1 || lista_intoarcere[stiva_muchii.top().second]<lista_nivel[stiva_muchii.top().first])&&stiva_muchii.size()>1)
            {
                componenta_biconexa.insert(stiva_muchii.top().second);
                componenta_biconexa.insert(stiva_muchii.top().first);
                cout<<stiva_muchii.top().first<<" "<<stiva_muchii.top().second<<"\n";

                stiva_muchii.pop();

            }
            if(stiva_muchii.size()>1)
            {
                componenta_biconexa.insert(stiva_muchii.top().second);
                componenta_biconexa.insert(stiva_muchii.top().first);
                set<int, less<int> >::iterator itr;
            for(itr=componenta_biconexa.begin();itr!=componenta_biconexa.end();itr++)
                    fout<<*itr<<" ";
                fout<<"\n";
            componenta_biconexa.clear();
            stiva_muchii.pop();
            }
            else
            {
                set<int, less<int> >::iterator itr;
                for(itr=componenta_biconexa.begin();itr!=componenta_biconexa.end();itr++)
                    fout<<*itr<<" ";
                fout<<"\n";
                componenta_biconexa.clear();
            }
        }
    }
}
void Graf_Neorientat::dfs_biconex(int nod,int viz[],int lista_intoarcere[],int lista_nivel[],int nivel,int mat[],stack<pair<int,int>> &stiva_muchii,unordered_map<int,vector<int>> &lista_fii)
{
        viz[nod] = 1;
        lista_nivel[nod] = nivel;
        lista_intoarcere[nod] = nivel;
        int nr_noduri2 = Graf_Neorientat::get_nr_noduri()+1;
        if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
        {
            for(int i=1;i<=lista_adiacenta[nod].size();i++)
                if(viz[lista_adiacenta[nod][i-1]]==0)
                {
                    //cout<<nod<<" "<<lista_adiacenta[nod][i-1]<<"\n";
                    lista_fii[nod].push_back(lista_adiacenta[nod][i-1]);
                    mat[lista_adiacenta[nod][i-1]*nr_noduri2 + nod] = 1;
                    mat[nod*nr_noduri2 + lista_adiacenta[nod][i-1]] =1;
                    pair<int,int> muchie_curenta;
                    muchie_curenta.first = nod;
                    muchie_curenta.second = lista_adiacenta[nod][i-1];
                    stiva_muchii.push(muchie_curenta);
                    dfs_biconex(lista_adiacenta[nod][i-1],viz,lista_intoarcere,lista_nivel,nivel+1,mat,stiva_muchii,lista_fii);
                    lista_intoarcere[nod] = min(lista_intoarcere[nod],lista_intoarcere[lista_adiacenta[nod][i-1]]);
                }
                else
                {
                    if(mat[nod* nr_noduri2 + lista_adiacenta[nod][i-1]]==0)
                    lista_intoarcere[nod] = min(lista_intoarcere[nod],lista_intoarcere[lista_adiacenta[nod][i-1]]);//might need some remaking
                }
        }
}
int Graf_Neorientat::begin_biconex()
{
    int nr_componente_biconexe =0;
    int lista_nivel[Graf_Neorientat::get_nr_noduri()+1];
    int lista_intoarcere[Graf_Neorientat::get_nr_noduri()+1];
    int lista_noduri_critice[Graf_Neorientat::get_nr_noduri()+1]={0};
    int viz[Graf_Neorientat::get_nr_noduri()+1]={0};
    int matrice_muchii_dfs[(Graf_Neorientat::get_nr_noduri()+1)*(Graf_Neorientat::get_nr_noduri()+1)] ={0};
    stack<pair<int,int>> stiva_muchii_dfs;
    unordered_map<int,vector<int>> lista_fii;
    dfs_biconex(1,viz,lista_intoarcere,lista_nivel,0,matrice_muchii_dfs,stiva_muchii_dfs,lista_fii);
    for(int i=1;i<=Graf_Neorientat::get_nr_noduri()+1;i++)
    {
        if(lista_fii.find(i)!=lista_fii.end())
            for(int j=0;j<lista_fii[i].size();j++)
                if(lista_intoarcere[lista_fii[i][j]]>=lista_nivel[i])
                {
                    lista_noduri_critice[i]=1;
                    break;
                }
    }
        while(!stiva_muchii_dfs.empty())

    {

        if(lista_noduri_critice[stiva_muchii_dfs.top().first]==1 && lista_intoarcere[stiva_muchii_dfs.top().second]>=lista_nivel[stiva_muchii_dfs.top().first])
            nr_componente_biconexe++;
        stiva_muchii_dfs.pop();

    }
    fout<<nr_componente_biconexe<<"\n";
    set<int,less<int>> componenta_biconexa;
    stack<pair<int,int>> stiva_muchii_dfs_curenta;
    int viz2[Graf_Neorientat::get_nr_noduri()+1] = {0};
    dfs_biconex_stiva(1,viz2,lista_intoarcere,lista_nivel,stiva_muchii_dfs_curenta,componenta_biconexa,lista_noduri_critice);


    cout<<"Lista nivel ";
    for(int i=1;i<=Graf_Neorientat::get_nr_noduri();i++)
        cout<<i<<":"<<lista_nivel[i]<<" ";
    cout<<"\n\nLista intoarcere ";
    for(int i=1;i<=Graf_Neorientat::get_nr_noduri();i++)
        cout<<lista_intoarcere[i]<<" ";
    cout<<"\n\nLista noduri critice ";

    for(int i=1;i<=Graf_Neorientat::get_nr_noduri();i++)
        if(lista_noduri_critice[i]==1)
            cout<<i<<" ";
    cout<<"\n\n";






    return 1;




}
void Graf_Neorientat::bfs(int nod_start)
{
    int viz[Graf::get_nr_noduri()+1]={0};
    ofstream fout("bfs.out");
    int contor = 0;
    int distanta[Graf::get_nr_noduri()+1]={-1};
    queue<int> bfs_queue;
    bfs_queue.push(nod_start);
    viz[nod_start] = 1;
    while(!bfs_queue.empty())
    {
        contor++;
        int front_queue = bfs_queue.front();
        if(lista_adiacenta.find(front_queue)!=lista_adiacenta.end())
        {
            for(int i=1;i<=lista_adiacenta[front_queue].size();i++)
            {
                if(viz[lista_adiacenta[front_queue][i-1]]==0)
                {
                    bfs_queue.push(lista_adiacenta[front_queue][i-1]);
                    distanta[lista_adiacenta[front_queue][i-1]]=contor;
                    viz[lista_adiacenta[front_queue][i-1]]=1;
                }
            }
        }
        bfs_queue.pop();
    }
    distanta[nod_start] = 0;
    for(int i=1;i<=Graf::get_nr_noduri();i++)
        fout<<distanta[i]<<" ";
}
void Graf_Neorientat::dfs(int nod,int viz[])
{
        viz[nod] = 1;
        if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
        {
            for(int i=1;i<=lista_adiacenta[nod].size();i++)
                if(viz[lista_adiacenta[nod][i-1]]==0)
                    dfs(lista_adiacenta[nod][i-1],viz);
        }

}
int Graf_Neorientat::begin_dfs()
{
    int viz[Graf::get_nr_noduri()+1] ={0};
    int contor=0;
    for(int i=1;i<=Graf::get_nr_noduri();i++)
        if(viz[i]==0)
    {
        contor++;
        Graf_Neorientat::dfs(i,viz);
    }
    return contor;

}
void Graf_Neorientat::scrie_tip_graf()
{
    cout<<"\nGraf Neorientat";
}
int Graf_Neorientat::get_nr_muchii()
{
    return this -> numar_muchii;
}
unordered_map<int,vector<int>> Graf_Neorientat::get_lista_adiacenta()
{
    return this -> lista_adiacenta;
}
Graf_Neorientat::Graf_Neorientat():Graf()
{
    this -> numar_muchii = 0;
}
Graf_Neorientat::Graf_Neorientat(int nr_noduri,int numar_muchii,unordered_map <int,vector<int>> lista_adiacenta):Graf(nr_noduri)
{
    this->numar_muchii = numar_muchii;
    this->lista_adiacenta = lista_adiacenta;
}
Graf_Neorientat::Graf_Neorientat(const Graf_Neorientat& g):Graf(g)
{
    this -> numar_muchii = g.numar_muchii;
    this -> lista_adiacenta= g.lista_adiacenta;
}
Graf_Neorientat& Graf_Neorientat::operator=(const Graf_Neorientat& g)
{
    if(this!= &g)
    {
        Graf::operator=(g);
        this->numar_muchii = g.numar_muchii;
        this->lista_adiacenta = g.lista_adiacenta;
    }
    *this;
}

ifstream& Graf_Neorientat::citire_graf_virtuala_fisier(ifstream& in)
{
    Graf::citire_graf_virtuala_fisier(in);
    in>>this->numar_muchii;
    for(int i=1;i<=this->numar_muchii;i++)
    {
        int first,second;
        in>>first>>second;
        lista_adiacenta[first].push_back(second);
        lista_adiacenta[second].push_back(first);
    }
    return in;
}
ifstream& operator>>(ifstream& in,Graf_Neorientat& g)
{
    return g.citire_graf_virtuala_fisier(in);
}
Graf_Neorientat::~Graf_Neorientat(){}

class Graf_Orientat:public Graf
{
private:
    int numar_muchii;
    unordered_map<int,vector<int>>lista_adiacenta;
public:
    //constructori
    Graf_Orientat();
    Graf_Orientat(int nr_noduri,int numar_muchii,unordered_map <int,vector<int>> lista_adiacenta);
    //operatorii de copiere
    Graf_Orientat(const Graf_Orientat& g);
    Graf_Orientat& operator=(const Graf_Orientat& g);
    //functiile de cititre si afisare
    friend ifstream& operator>>(ifstream& in,Graf_Orientat& g);
    //destructorul
    ~Graf_Orientat();
    //functie virtuala pura
    virtual void scrie_tip_graf();
    virtual int begin_dfs();
    void dfs(int nod, int viz[]);
    virtual void bfs(int nod_start);
    //setteri si getteri
    int get_nr_muchii();
    unordered_map<int,vector<int>> get_lista_adiacenta();


    //citire si afisare virtuala
    virtual ifstream& citire_graf_virtuala_fisier(ifstream& in);


};
void Graf_Orientat::bfs(int nod_start)
{
    int viz[Graf::get_nr_noduri()+1]={0};
    ofstream fout("bfs.out");
    int contor = 1;
    int distanta[Graf::get_nr_noduri()+1];
    for(int i=1;i<=Graf::get_nr_noduri();i++)
        distanta[i]=-1;
    queue<int> bfs_queue;
    bfs_queue.push(nod_start);
    viz[nod_start] = 1;
    distanta[nod_start]=0;
    while(!bfs_queue.empty())
    {

        int front_queue = bfs_queue.front();
        if(lista_adiacenta.find(front_queue)!=lista_adiacenta.end())
        {
            for(int i=1;i<=lista_adiacenta[front_queue].size();i++)
            {
                if(viz[lista_adiacenta[front_queue][i-1]]==0)
                {
                    bfs_queue.push(lista_adiacenta[front_queue][i-1]);
                    distanta[lista_adiacenta[front_queue][i-1]]=distanta[front_queue]+1;
                    viz[lista_adiacenta[front_queue][i-1]]=1;
                    cout<<"\n"<<front_queue<<" "<<lista_adiacenta[front_queue][i-1]<<" "<<contor;

                }
            }
        }
        bfs_queue.pop();
    }
    distanta[nod_start] = 0;
    for(int i=1;i<=Graf::get_nr_noduri();i++)
        fout<<distanta[i]<<" ";
}
void Graf_Orientat::dfs(int nod,int viz[])
{
        viz[nod] = 1;
        if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
        {
            for(int i=1;i<=lista_adiacenta[nod].size();i++)
                if(viz[lista_adiacenta[nod][i-1]]==0)
                    dfs(lista_adiacenta[nod][i-1],viz);
        }

}
int Graf_Orientat::begin_dfs()
{
    int viz[Graf::get_nr_noduri()+1] ={0};
    int contor=0;
    for(int i=1;i<=Graf::get_nr_noduri();i++)
        if(viz[i]==0)
    {
        contor++;
        Graf_Orientat::dfs(i,viz);
    }
    return contor;

}
void Graf_Orientat::scrie_tip_graf()
{
    cout<<"\nGraf Orientat";
}
int Graf_Orientat::get_nr_muchii()
{
    return this -> numar_muchii;
}
unordered_map<int,vector<int>> Graf_Orientat::get_lista_adiacenta()
{
    return this -> lista_adiacenta;
}
Graf_Orientat::Graf_Orientat():Graf()
{
    this -> numar_muchii = 0;
}
Graf_Orientat::Graf_Orientat(int nr_noduri,int numar_muchii,unordered_map <int,vector<int>> lista_adiacenta):Graf(nr_noduri)
{
    this->numar_muchii = numar_muchii;
    this->lista_adiacenta = lista_adiacenta;
}
Graf_Orientat::Graf_Orientat(const Graf_Orientat& g):Graf(g)
{
    this -> numar_muchii = g.numar_muchii;
    this -> lista_adiacenta= g.lista_adiacenta;
}
Graf_Orientat& Graf_Orientat::operator=(const Graf_Orientat& g)
{
    if(this!= &g)
    {
        Graf::operator=(g);
        this->numar_muchii = g.numar_muchii;
        this->lista_adiacenta = g.lista_adiacenta;
    }
    *this;
}

ifstream& Graf_Orientat::citire_graf_virtuala_fisier(ifstream& in)
{
    Graf::citire_graf_virtuala_fisier(in);
    in>>this->numar_muchii;
    for(int i=1;i<=this->numar_muchii;i++)
    {
        int first,second;
        in>>first>>second;
        lista_adiacenta[first].push_back(second);
    }
    return in;
}
ifstream& operator>>(ifstream& in,Graf_Orientat& g)
{
    return g.citire_graf_virtuala_fisier(in);
}
Graf_Orientat::~Graf_Orientat(){}


int main()
{
    //exercitiul DFS
       /* ifstream fin("dfs.in");
        ofstream fout("dfs.out");
        Graf_Neorientat g;
        fin>>g;
        fout<<g.begin_dfs();*/

    //exercitiul BFS
       /* ifstream fin("bfs.in");
        ofstream fout("bfs.out");
        int nr_noduri,nr_muchii,nod_start;
        unordered_map<int,vector<int>> lista_adiacenta;
        fin>>nr_noduri>>nr_muchii>>nod_start;
        for(int i=0;i<nr_muchii;i++)
        {
            int first,second;
            fin>>first>>second;
            lista_adiacenta[first].push_back(second);
        }
        Graf_Orientat g(nr_noduri,nr_muchii,lista_adiacenta);
        g.bfs(nod_start);*/

    //exerctiul Biconexe
        ifstream fin("biconex.in");
        Graf_Neorientat g;
        fin>>g;
        g.begin_biconex();






    return 0;
}