#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <deque>
#define PROBLEMA 3
using namespace std;
ifstream f;
ofstream g;
class graf
{
    unsigned int n,m,s;
    vector< vector<unsigned int> > lista_vecini;
    vector <int> grad;
public:
    graf(const unsigned int &);
    ~graf();
    void setn(const unsigned int &);
    void setm(const unsigned int &);
    void sets(const unsigned int &);
    int getn();
    int getm();
    int gets();
    void getvecini();
    void sortvecini();
    void BFS();
    void DFS(unsigned int);
    void biconex(unsigned int);
    void ctc(unsigned int);
    void sortaret(unsigned int);
    void havelhakimi();
    vector<vector<int>> criticalConnections(int,vector<vector<int>>&);
};


graf::graf(const unsigned int &opt=0)
{

    switch (opt)
    {
    case 1:
    case 3:
    {
        unsigned int x,y;
        f>>this->n>>this->m;
        if (opt==1) f>>this->s;
        this->lista_vecini.resize(n+1);
        for (unsigned int i=0; i<this->m; ++i)
        {
            f>>x>>y;
            this->lista_vecini[x].push_back(y);
        }
        break;
    }
    case 2:
    {
        unsigned int x,y;
        f>>this->n>>this->m;
        this->lista_vecini.resize(n+1);
        for (unsigned int i=0; i<this->m; ++i)
        {
            f>>x>>y;
            this->lista_vecini[x].push_back(y);
            this->lista_vecini[y].push_back(x);
        }
        break;
    }
    case 4:
    {
        unsigned int x;
        while (f>>x)
            this->grad.push_back(x);
        break;
    }
    default:
        break;
    }
}

graf::~graf()
{
    //simbolic
    this->n=this->m=this->s=0;
    for (size_t i=0; i<this->lista_vecini.size(); ++i)
        this->lista_vecini[i].clear();
    this->lista_vecini.clear();
    this->grad.clear();
}

void graf::setn(const unsigned int &n)
{
    this->n=n;
}

void graf::setm(const unsigned int &m)
{
    this->m=m;
}

void graf::sets(const unsigned int &s)
{
    this->s=s;
}

int graf::getm()
{
    return this->m;
}

int graf::getn()
{
    return this->n;
}

int graf::gets()
{
    return this->s;
}

void graf::getvecini()
{
    for (unsigned int i=1-min(1,int(lista_vecini[0].size())); i<this->lista_vecini.size()-min(1,int(lista_vecini[0].size())); ++i)
    {
        cout<<i<<": ";
        for (unsigned int j=0; j<this->lista_vecini[i].size(); ++j)
            cout<<this->lista_vecini[i][j]<<" ";
        cout<<"\n";
    }
}

void graf::sortvecini()
{
    unsigned int j,k;
    unsigned int ap[this->n+1];
    for (j=0; j<=this->n; ++j)
        ap[j]=0;
    for (unsigned int i=1; i<this->lista_vecini.size(); ++i)
    {
        k=0;
        for (j=0; j<this->lista_vecini[i].size(); ++j)
            ++ap[this->lista_vecini[i][j]];
        for (j=1; j<=this->n; ++j)
        {
            if (ap[j])
            {
                this->lista_vecini[i][k++]=j;
                ap[j]=0;
            }
        }
    }
}

void graf::BFS()
{
    int d[this->n+1];
    for (unsigned int i=1; i<=this->n; ++i)
        d[i]=-1;
    bool viz[this->n+1];
    for (unsigned int i=1; i<=this->n; ++i)
        viz[i]=false;
    unsigned int index=0;
    vector <int> coada;
    coada.push_back(this->s);
    d[this->s]=0;
    viz[this->s]=true;
    while (index<coada.size())
    {
        int nod_curent=coada[index++];
        for (unsigned int i=0; i<this->lista_vecini[nod_curent].size(); ++i)
            if (!viz[this->lista_vecini[nod_curent][i]])
            {
                coada.push_back(this->lista_vecini[nod_curent][i]);
                viz[this->lista_vecini[nod_curent][i]]=true;
                d[this->lista_vecini[nod_curent][i]]=d[nod_curent]+1;
            }
    }
    for (unsigned int i=1; i<=this->n; ++i)
    {
        g<<d[i]<<" ";
    }
}

void graf::DFS(unsigned int nod_curent)
{
    static bool *viz=new bool[this->n+1];
    static unsigned int nrconex;
    if (nod_curent==0)
    {
        for (unsigned int i=1; i<=this->n; ++i)
            viz[i]=false;
        nrconex=0;
        for (unsigned int i=1; i<=this->n; ++i)
            if (!viz[i])
            {
                nrconex++;
                DFS(i);
            }
        g<<nrconex;
        delete [] viz;
    }
    else
    {
        viz[nod_curent]=true;
        for (unsigned int i=0; i<this->lista_vecini[nod_curent].size(); ++i)
            if (!viz[this->lista_vecini[nod_curent][i]])
                DFS(this->lista_vecini[nod_curent][i]);
    }
}

void graf::biconex(unsigned int nod_curent)
{
    static int *niv=new int[this->n+1];
    static int *niv_int=new int[this->n+1];
    static unsigned int nrbiconex=0;
    static stack <pair<unsigned int,unsigned int>> stiva;
    static vector <unsigned int> sol;
    unsigned int i;
    if (nod_curent==0)
    {
        for (i=1; i<=this->n; ++i)
        {
            niv[i]=-1;
            niv_int[i]=0;
        }
        niv[1]=0;
        biconex(1);
        g<<nrbiconex<<"\n";
        for (auto i = sol.begin(); i != sol.end(); ++ i)
            if (*i!=0)
                g<<*i<<" ";
            else
                g<<"\n";
        delete [] niv;
        delete [] niv_int;
    }
    else
    {
        for (unsigned int i=0; i<this->lista_vecini[nod_curent].size(); ++i)
            if (niv[this->lista_vecini[nod_curent][i]]==-1)
            {
                niv[this->lista_vecini[nod_curent][i]]=niv[nod_curent]+1;
                niv_int[this->lista_vecini[nod_curent][i]]=niv[nod_curent]+1;
                stiva.push(make_pair(nod_curent,this->lista_vecini[nod_curent][i]));
                biconex(this->lista_vecini[nod_curent][i]);
                niv_int[nod_curent]=min(niv_int[nod_curent],niv_int[this->lista_vecini[nod_curent][i]]);
                if (niv_int[this->lista_vecini[nod_curent][i]]>=niv[nod_curent])
                {
                    nrbiconex++;
                    unordered_map<unsigned int,bool> ap;
                    unsigned int aux1;
                    unsigned int aux2;
                    do
                    {

                        aux1=stiva.top().first;
                        aux2=stiva.top().second;
                        if (!ap[aux1])
                        {
                            sol.push_back(aux1);
                            ap[aux1]=1;
                        }
                        if (!ap[aux2])
                        {
                            sol.push_back(aux2);
                            ap[aux2]=1;
                        }
                        stiva.pop();
                    }
                    while(aux1!=nod_curent || aux2!=this->lista_vecini[nod_curent][i]);
                    sol.push_back(0);
                }
            }
            else if (niv[nod_curent]-1!=niv[this->lista_vecini[nod_curent][i]])
                niv_int[nod_curent]=min(niv_int[nod_curent],niv[this->lista_vecini[nod_curent][i]]);
        //scadem 1 ca sa nu luam in considerare si tatal nodului
    }
}

void graf::ctc(unsigned int nod_curent)
{
    static int *indx=new int[this->n+1];
    static int *indx_min=new int[this->n+1];
    static bool *peStiva=new bool[this->n+1];
    static unsigned int nrctc=0;
    static stack <unsigned int> stiva;
    static vector <unsigned int> sol;
    static unsigned int it=1;
    unsigned int nod_aux;
    unsigned int i;
    if (nod_curent==0)
    {
        for (i=1; i<=this->n; ++i)
        {
            indx[i]=-1;
            indx_min[i]=0;
            peStiva[i]=false;
        }
        for(int i=1; i<=this->n; ++i)
            if (indx[i]==-1)
                ctc(i);
        g<<nrctc<<"\n";
        for (auto i = sol.begin(); i != sol.end(); ++ i)
            if (*i!=0)
                g<<*i<<" ";
            else
                g<<"\n";
        delete [] indx;
        delete [] indx_min;
        delete [] peStiva;
    }
    else
    {
        indx[nod_curent]=it;
        indx_min[nod_curent]=it++;
        stiva.push(nod_curent);
        peStiva[nod_curent]=true;
        cout<<nod_curent<<"\n";
        for (unsigned int i=0; i<this->lista_vecini[nod_curent].size(); ++i)
            if (indx[this->lista_vecini[nod_curent][i]]==-1)
            {
                ctc(this->lista_vecini[nod_curent][i]);
                indx_min[nod_curent]=min(indx_min[nod_curent],indx_min[this->lista_vecini[nod_curent][i]]);
            }
            else if (peStiva[this->lista_vecini[nod_curent][i]])
                indx_min[nod_curent]=min(indx_min[nod_curent],indx[this->lista_vecini[nod_curent][i]]);
        if (indx_min[nod_curent]==indx[nod_curent])
        {
            ++nrctc;
            do
            {
                nod_aux=stiva.top();
                peStiva[nod_aux]=false;
                sol.push_back(nod_aux);
                stiva.pop();
            }
            while (nod_aux!=nod_curent);
            sol.push_back(0);
        }

    }
}

void graf::sortaret(unsigned int nod_curent)
{
    static bool *viz=new bool[this->n+1];
    static stack <unsigned int> sol;
    if (nod_curent==0)
    {
        unsigned int i;
        for (i=1; i<=this->n; ++i)
            viz[i]=false;
        for (i=1; i<=this->n; ++i)
            if (!viz[i])
                sortaret(i);
        while (!sol.empty())
        {
            //afisam in postordine invers
            g<<sol.top()<<" ";
            sol.pop();
        }
        delete [] viz;
    }
    else
    {
        viz[nod_curent]=true;
        for (unsigned int i=0; i<this->lista_vecini[nod_curent].size(); ++i)
            if (!viz[lista_vecini[nod_curent][i]])
            {
                sortaret(lista_vecini[nod_curent][i]);
            }
        //introducem nodurile in postordine (dupa ce ies din stiva) in stiva
        sol.push(nod_curent);
    }
}

void graf::havelhakimi()
{
    bool zero=false;
    while (!zero)
    {
        zero=true;
        sort(this->grad.begin(),this->grad.end());
        unsigned int nrs=this->grad[this->grad.size()-1];
        this->grad.pop_back();
        if (nrs>this->grad.size())
        {
            cout<<"Nu";
            g<<"Nu";
            return;
        }
        for (unsigned int i=this->grad.size()-1; (int)(i)>(int)(this->grad.size()-nrs-1); --i)
        {
            --grad[i];
            if (grad[i]<0)
            {
                cout<<"Nu";
                g<<"Nu";
                return;
            }
            if (grad[i]!=0)
                zero=false;
        }
    }
    cout<<"Da";
    g<<"Da";
}

vector<vector<int>> graf::criticalConnections(int n, vector<vector<int>>& connections)
{
    unsigned int i;
    this->setn(n);
    this->setm(connections.size());
    stack <unsigned int> stiva;
    vector<vector<int>> sol;
    unsigned int icopil[n];
    this->lista_vecini.clear();
    this->lista_vecini.resize(n);
    int niv[n];
    int niv_int[n];
    for (i=0; i<n; ++i)
    {
        niv[i]=-1;
        niv_int[i]=0;
        icopil[i]=0;
    }
    for (i=0; i<connections.size(); ++i)
    {
        this->lista_vecini[connections[i][0]].push_back(connections[i][1]);
        this->lista_vecini[connections[i][1]].push_back(connections[i][0]);
    }
    niv[0]=1;
    stiva.push(0);
    while (!stiva.empty())
    {
        unsigned int nod_curent=stiva.top();
        for (i=icopil[nod_curent]; i<lista_vecini[nod_curent].size(); ++i)
        {
            ++icopil[nod_curent];
            if (niv[lista_vecini[nod_curent][i]]==-1)
            {
                niv[lista_vecini[nod_curent][i]]=niv[nod_curent]+1;
                niv_int[lista_vecini[nod_curent][i]]=niv[nod_curent]+1;
                stiva.push(lista_vecini[nod_curent][i]);
                nod_curent=lista_vecini[nod_curent][i];
                break;
            }
            else if (niv[nod_curent]-1!=niv[lista_vecini[nod_curent][i]])
                niv_int[nod_curent]=min(niv_int[nod_curent],niv[lista_vecini[nod_curent][i]]);
        }
        if (icopil[nod_curent]==lista_vecini[nod_curent].size())
        {
            unsigned int copil=stiva.top();
            stiva.pop();
            if (!stiva.empty())
            {
                niv_int[stiva.top()]=min(niv_int[copil],niv_int[stiva.top()]);
                if (niv_int[copil]>niv[stiva.top()])
                    sol.push_back({int(stiva.top()),int(copil)});
            }

        }
    }
    return sol;
}

int main()
{
    switch (PROBLEMA)
    {
    case 1:
    {
        f.open ("bfs.in", std::ifstream::in);
        g.open ("bfs.out", std::ifstream::out);
        graf a(1);
        a.sortvecini();
        a.BFS();
        f.close();
        g.close();
        break;
    }
    case 2:
    {
        f.open ("dfs.in", std::ifstream::in);
        g.open ("dfs.out", std::ifstream::out);
        graf a(2);
        a.sortvecini();
        a.DFS(0);
        f.close();
        g.close();
        break;
    }
    case 3:
    {
        f.open("biconex.in",std::fstream::in);
        g.open("biconex.out",std::fstream::out);
        graf a(2);
        a.biconex(0);
        f.close();
        g.close();
        break;
    }
    case 4:
    {
        f.open("ctc.in",std::fstream::in);
        g.open("ctc.out",std::fstream::out);
        graf a(3);
        a.ctc(0);
        f.close();
        g.close();
        break;
    }
    case 5:
    {
        f.open("sortaret.in",std::fstream::in);
        g.open("sortaret.out",std::fstream::out);
        graf a(3);
        a.sortaret(0);
        f.close();
        g.close();
        break;
    }
    case 6:
    {
        f.open("havelhakimi.in",std::fstream::in);
        g.open("havelhakimi.out",std::fstream::out);
        graf a(4);
        a.havelhakimi();
        f.close();
        g.close();
        break;
    }
    case 7:
    {
        f.open("criticalConnections.in",std::fstream::in);
        g.open("criticalConnections.out",std::fstream::out);
        graf a;
        vector<vector<int>> muchii;
        int n,x,y,m;
        unsigned int nrt;
        f>>nrt;
        for (unsigned int t=0; t<nrt; ++t)
        {
            muchii.resize(0);
            f>>n>>m;
            for (int i=0; i<m; ++i)
            {
                f>>x>>y;
                muchii.push_back(vector<int> {x,y});
            }
            vector<vector<int>> sol(a.criticalConnections(n,muchii));
            for (size_t i=0; i<sol.size(); ++i)
            {
                cout<<"("<<sol[i][0]<<","<<sol[i][1]<<") ";
                g<<"("<<sol[i][0]<<","<<sol[i][1]<<") ";
            }
            cout<<"\n\n";
            g<<"\n\n";
        }
        f.close();
        g.close();
        break;
    }
    default:
        break;
    }
}