#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");


struct nod{

nod *next;
int val;

};

class OrientedGraph{

protected:
    nod *varfuri[100001];
    int nrVarfuri;
    int nrMuchii;
    int varfStart;
    int vizitat[100001];

public:
    OrientedGraph(){
        vizitAll();
    }

    OrientedGraph(int nrV, int nrM): nrVarfuri(nrV), nrMuchii(nrM){}

void vizitAll(){
        for(int i = 0;i<100001;++i){
            vizitat[i] = 0;
        }
}

void citire(){
    if(!nrVarfuri)fin>>nrVarfuri>>nrMuchii; /// default behavior
    for(int i = 1;i<=nrMuchii;++i){
        int x, y;
        fin>>x>>y;

        nod *p = new nod;
        p->val = y;
        p->next = varfuri[x];
        varfuri[x] = p;

    }
}

void afisare(){

    for(int i = 1;i<=nrVarfuri;++i){
        nod *p = varfuri[i];
        cout<<"varf: "<<i<<"...: ";
        while(p){
            cout<<p->val<<" ";
            p = p->next;
        }
        cout<<endl;
    }

}


};

class BfsGraph: public OrientedGraph{

public:
    BfsGraph(): OrientedGraph(){}
    BfsGraph(int nrV, int nrM): OrientedGraph(nrV, nrM){}

void bfs(int startNo){

    int coada[100003], prim, ultim, i;
    prim = ultim = 1;
    coada[1] = startNo;
    vizitat[startNo] = 1;

    while(prim <= ultim){
        int nodAcutal = coada[prim];
        prim++;

        nod *p = varfuri[nodAcutal];
        while(p){

            if(vizitat[p->val] == 0){
                vizitat[p->val] = vizitat[nodAcutal] + 1;
                ++ultim;
                coada[ultim] = p->val;
            }

            p = p->next;
        }

    }

    for(int i = 1;i<=nrVarfuri;++i)fout<<vizitat[i] - 1<<" ";


}

};


int main()
{
    int n, m, startNod;
    fin>>n>>m>>startNod;
    BfsGraph g(n, m);
    g.citire();
    g.bfs(startNod);


    return 0;
}