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

using namespace std;

class Graf{
private:
    int m_nrNoduri;
    vector<vector<int>> m_listAdiacenta;
public:
    void citireGrafNeorientat(char *fisier);
    void citireGrafOrientat(char *fisier);

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

    vector<int> createViz(int val);
    void afisDrumuriMinime(vector<int> drumurileMinime);
    /*int numaraComponenteConexe();
    void afisComponenteTareConexe();*/

    int citireBFSINfoarena();
};

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;
}

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

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
    vector<int> viz = this->createViz(0);
        //adaugam nodul sursa in coada si il marcam ca si vizitat
    coada.push(nod);
    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(viz[this->m_listAdiacenta[curent][i]] == 0){
                coada.push(this->m_listAdiacenta[curent][i]);
                distante[coada.back()] = distante[curent]+1;
                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<<" ";
    }
}

int main()
{
    int nodPornire;
    Graf g;

    nodPornire = g.citireBFSINfoarena();

    g.BFS(nodPornire);
    return 0;
}