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


using namespace std;


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();
    //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_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);





    return 0;
}