/* Aplicații ale BFS:
Găsirea celui mai scurt drum în grafuri neponderate.
Verificarea conectivității într-un graf.
Detectarea ciclicității în grafuri neorientate. */

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

using namespace std;



class Graf
{
public:
    int N, M; //nr de noduri/muchii
    int orientat; //0 orientat, 1 neorientat
    vector<list<int>> listaAdiacenta;
    vector<bool> vizitat;
    vector<int> tata; //vector de tati pt arborele BFS
    vector<int> distanta; //d [j] = lungimea drumului determinat de algoritm de la s la j == nivelul lui j în arborele asociat parcurgerii = distanța de la s la j
    

    // vector<list<int>> ListaAdiacenta(int N, int M)
    // {
    //     //ifstream f(numeFisier);
    //     int nod1, nod2;
    //     //f>>N>>M;
    //     vector<list<int>> listaAd(N+1); //n+1 ptc primul nod e 1 si ultimul n

    //     while(f>>nod1>>nod2)
    //     {
    //         listaAd[nod1].push_back(nod2); //adaug la lista nodului nod1, nodul cu care e adiacent

    //         if(orientat==0)
    //             listaAd[nod2].push_back(nod1);
    //     }
        
    //     return listaAd;
    // }

    Graf(int N, int M, int orientat)
    {
        this->N=N;
        this->M=M;
        this->orientat=orientat;
        listaAdiacenta.resize(N+1);//n+1 ptc primul nod e 1 si ultimul n
        tata.resize(N+1);
        distanta.assign(N+1,-1);
        vizitat.assign(N+1,false);

    }


    // Adaugă o muchie între nodurile u și v
    void AdaugaMuchie(int u, int v) 
    {
        listaAdiacenta[u].push_back(v); // Adăugăm v în lista de adiacență a lui u
        if(orientat==1)
            listaAdiacenta[v].push_back(u); // Dacă graful este neorientat, adăugăm u în lista lui v
    }


    void AfisareListaAd()
    {
        for(int i=1; i<=N; i++)
            //if(!listaAdiacenta[i].empty()) //daca lista nodului i nu e vida, o afisez
            {
                cout<<i<<" : ";
                for(int nod : listaAdiacenta[i])
                    cout<<nod<<" ";
                cout<<endl;
            }
    }

    // Funcția BFS(lista de adiacenta, nod de plecare)
    void BFS(int sursa) 
    {
        
        vizitat.assign(N, false);  // Vector de noduri vizitate
        queue<int> coada;  // Coada pentru BFS
        
        // Pornim de la nodul sursă
        vizitat[sursa] = true;
        distanta[sursa] = 0;
        coada.push(sursa);
        
        while (!coada.empty()) 
        {
            int nodCurent = coada.front();
            coada.pop(); //scoate primul element
            
            //cout << nodCurent << " ";  // Afișăm nodul curent
            
            // Parcurgem toți vecinii nodului curent
            for (int vecin : listaAdiacenta[nodCurent]) 
            {
                if (!vizitat[vecin]) 
                {
                    vizitat[vecin] = true;
                    coada.push(vecin);
                    tata[vecin]=nodCurent;
                    distanta[vecin] = distanta[nodCurent] + 1;
                }
            }
        }
        
        cout << endl;
        
    }

    void BFScomplet()
    {
        //pt toate componentele conexe
        for(int x=1; x<=N; x++)
            if(vizitat[x]==0)
                BFS(x);
    }

};



ifstream f("bfs.in");
ofstream g("bfs.out");
int main() 
{
    int N,M,S,u,v;
    f>>N>>M>>S;
   
    Graf graf(N,M,0);

    for(int i=1; i<=M; i++)
    {
        f>>u>>v;
       
        graf.AdaugaMuchie(u,v);
    }
  


    graf.BFS(S);
    for(int i=1; i<=N; i++)
       g<<graf.distanta[i]<<" ";
    return 0;
}