#include <iostream>
#include <fstream>

using namespace std;

ifstream f("bfs.in");
ofstream f2("bfs.out");

struct Nod{
    int info;
    Nod * next;
};

int a[10000][10000], viz[1000], coada[1000], finale[1000], n, m, x, y, i, s, prim = 1, ultim = 1, el;

Nod listadeAdiacenta[1000];

void adaugare(Nod * prim, int z){
    Nod * newNode = new Nod;
    newNode -> info = z;
    newNode -> next = NULL;
    Nod * it = prim;
    while(it -> next != NULL){
        it = it -> next;
    }
    it -> next = newNode;
}

void bfs(){
    while(prim <= ultim){
        el = coada[prim];
        Nod * it = listadeAdiacenta[el].next;
        while(it != NULL){
            if(viz[it -> info] != 1){
                ultim++;
                coada[ultim] = it -> info;
                viz[it -> info] = 1;
                finale[it -> info] = finale[el] + 1;
                it = it -> next;
            }
            else{
                it = it -> next;
            }
        }
        prim = prim + 1;
    }
}

int main()
{
    f >> n >> m >> s;

    for(i = 1; i <= m; i++){
        f >> x >> y;

        Nod * listaX = &listadeAdiacenta[x];
        adaugare(listaX, y);
    }

    int prim = 1;
    int ultim = 1;

    coada[prim] = s;
    viz[s] = 1;
    finale[s] = 0;

    bfs();

    for(i = 1; i <= n; i++){
        if(viz[i] == 0){
            finale[i] = -1;
        }
    }

    for(i = 1; i <= n; i++){
        f2 << finale[i] << " ";
    }

    return 0;
}