#include <iostream>
#include <fstream>
#include <vector>
#define PROBLEMA 1
using namespace std;
ifstream f;
ofstream g;
class graf
{
    int n,m,s;
    vector< vector<int> > lista_vecini;
public:
    graf(unsigned int);
    int setn(const int x);
    int setm(const int x);
    int getn();
    int getm();
    int gets();
    void getvecini();
    void sortvecini();
    void BFS();
    void DFS(unsigned int);
    void biconex(unsigned int);
};


graf::graf(unsigned int opt)
{

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

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; i<this->lista_vecini.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()
{
    int j,k;
 unsigned int ap[this->n+1];
 for (j=0;j<=this->n;++j)
    ap[j]=0;
 for (int i=1;i<this->lista_vecini.size();++i)
 {
     k=0;
     for (j=0;j<lista_vecini[i].size();++j)
         ++ap[lista_vecini[i][j]];
     for (j=1;j<=this->n;++j)
     {
        if (ap[j])
        {
            lista_vecini[i][k++]=j;
            ap[j]=0;
        }
     }
 }
}

void graf::BFS()
{
    int d[this->n+1];
    for (int i=1; i<=n; ++i)
        d[i]=-1;
    bool viz[this->n+1];
    for (int i=1; i<=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 (int i=1; i<=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 (int i=1; i<=n; ++i)
            viz[i]=false;
        nrconex=0;
        for (int i=1; i<=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[lista_vecini[nod_curent][i]])
                DFS(lista_vecini[nod_curent][i]);
    }
}

void graf::biconex(unsigned int nod_curent)
{
    static bool *viz=new bool[this->n+1];
    static int *niv=new int[this->n+1];
    static int *niv_int=new int[this->n+1];
    static int *copil=new int[this->n+1];
    static unsigned int nrbiconex=0;
    vector <unsigned int> stiva;
    if (nod_curent==0)
    {
        for (int i=1; i<=n; ++i)
        {
            viz[i]=false;
            niv[i]=0;
            niv_int[i]=0;
            copil[i]=0;
        }
        biconex(1);
        for (int i=1;i<=n;++i)
        {
            cout<<niv[i]<<" ";

        }
        cout<<"\n";
        for (int i=1;i<=n;++i)
        {
            cout<<niv_int[i]<<" ";

        }
        cout<<"\n";
        cout<<nrbiconex;
        cout<<"Prelucram iar\n";
        for (int i=0;i<stiva.size();++i)
           cout<<stiva[i]<<" ";
        delete [] viz;
        delete [] niv;
        delete [] niv_int;
        delete [] copil;
    }
    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]])
            {
                niv[lista_vecini[nod_curent][i]]=niv[nod_curent]+1;
                niv_int[lista_vecini[nod_curent][i]]=niv[nod_curent]+1;
                copil[nod_curent]=lista_vecini[nod_curent][i];
                biconex(lista_vecini[nod_curent][i]);
                if (copil[nod_curent]!=0)
                    niv_int[nod_curent]=min(niv_int[nod_curent],niv_int[copil[nod_curent]]);
                    if (niv_int[copil[nod_curent]]>=niv[nod_curent])
                    {
                        cout<<"Nod critic: "<<nod_curent<<"\n";
                        nrbiconex++;
                        stiva.push_back(nod_curent);
                        stiva.push_back(0);
                    }

            }
            else if (niv_int[nod_curent]-1!=niv[lista_vecini[nod_curent][i]])
                niv_int[nod_curent]=min(niv_int[nod_curent],niv[lista_vecini[nod_curent][i]]);
                //scadem 1 ca sa nu luam in considerare si tatal nodului
            cout<<nod_curent<<"\n";
            stiva.push_back(nod_curent);
    }
}

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.sortvecini();
         a.getvecini();
         f.close();
         g.close();
        }
    default:
        break;
    }
}