#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

fstream fin("graf.in");
fstream bin("bfs.in");
//LAB 1-2 APLICATII PARCURGERI AF
//n nr de varf, m nr de muchii, lista muchiilor
//////////////MEMORAREA UNUI GRAF///////////////
// 1
//subprogram constr matrice de adiacenta citi din graf in
//subprogram afisare matrice de adiacenta

/*
void matrice_adiacenta_constr(const int& on, vector <vector <int>>& matrice)
{
    int n, m, x, y;
    fin>>n>>m;
    matrice = vector <vector <int>> (n, std::vector<int>(n,0));
    while(m)
    {
        fin>>x>>y;
        m--;
        matrice[x-1][y-1] = 1;
        if(on==1)
            matrice[y-1][x-1] = 1;
    }

}

void matrice_adiacenta_afisare(const vector<vector<int>>& matrice)
{
    for(auto i: matrice){
        for(auto j: i)
            cout<<j<<" ";
        cout<<'\n';
    }

}

void A1(){
    int on=-1;
    while(on < 0)
    {
        cout<<"Graful este: orientat(0) sau neorientat(1)?\n";
        cin>>on;
        if(on != 0 && on != 1)
            cout<<"Va rog introduceti doar 0 sau 1\n";
    }
    vector <vector <int>> matrice;
    matrice_adiacenta_constr(on,matrice);
    matrice_adiacenta_afisare(matrice);
    delete matrice;
}
*/


//2 liste adiacenta
void lista_adiacenta_constr(const int& on, vector <vector <int>>& lista, const int &n,const int &m)
{
    int x, y;
   //fin>>n>>m;
    lista = vector <vector <int>> (n);
    for(int i = 0; i<m; i++)
    {
        bin>>x>>y;

        lista[x-1].push_back(y);
        if(on==1)
            lista[y-1].push_back(x);
    }

}

void lista_adiacenta_afisare(const vector<vector<int>>& lista, const int& n)
{
    for(int i = 0; i < n; i++){
        cout<<i+1<<": ";

        for(int j = 0; j<lista[i].size(); j++)
                cout<<lista[i][j]<<" ";

        cout<<'\n';
    }

}

/*
void A2()
{
    int on=-1, n;
    while(on < 0)
    {
        cout<<"Graful este: orientat(0) sau neorientat(1)?\n";
        cin>>on;
        if(on != 0 && on != 1)
            cout<<"Va rog introduceti doar 0 sau 1\n";
    }
    vector <vector <int>> lista;
    lista_adiacenta_constr(on,lista, n);
    lista_adiacenta_afisare(lista, n);
}*/

////////////////PARCURGEREA IN LATIME BF//////////////
//n varf, m arce, s - radacina
//mr minim de arce ce trb oarcurse pt a ajunge din s la x


void B1(){
    int n,m,s,nod_curent, d = 0;
    bin>>n>>m>>s;
    vector<int> distanta(n,-1); //lista de distanta -2 nevizitat
    vector<int> vecini;
    vector<vector<int>> lista;//lista adiacenta
    lista_adiacenta_constr(0,lista,n,m);
    //lista_adiacenta_afisare(lista,n);
    distanta[s-1] = d++;
    nod_curent=s-1;
    vecini.push_back(nod_curent);

    while ( vecini.size() > 0)
    {
        for(auto j: lista[nod_curent]){
            //trb sa bagam in vecini doar aia nevizitati!
            if(distanta[j-1] == -1 && j != nod_curent){
                vecini.insert(vecini.begin(), j);
                distanta[j-1] = d;
            }


        }
        vecini.pop_back();

       /* for(auto j: vecini)
            cout<<j<<" ";
        cout<<" AAA "<<vecini.size();*/

        if(vecini.size() > 0){
            nod_curent=vecini.back()-1;
            d = distanta[nod_curent] + 1;
        }

    }

    for(auto j:distanta)
        cout<<j<<" ";


}

int main() {
        //A1();
        //A2();
        B1();
    return 0;
}