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

#define VALMAX 100005

using namespace std;

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


struct nod{

nod *next;
int val;

};

class OrientedGraph{

protected:
    nod *varfuri[VALMAX];
    int nrVarfuri;
    int nrMuchii;
    int varfStart;
    int vizitat[VALMAX + 1];

public:
    OrientedGraph(){
        vizitAll();
    }

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

void vizitAll(){
        for(int i = 1;i<=VALMAX;++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 prim, ultim, i;
    queue <int> q;
    q.push(startNo);

    vizitat[startNo] = 1;

    while (!q.empty()){
        int nodAcutal = q.front();
        q.pop();

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

            if(vizitat[p->val] == 0){
                vizitat[p->val] = vizitat[nodAcutal] + 1;
                q.push(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;
}