#include <iostream>
#include <fstream>

using namespace std;

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

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

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

Nod listadeAdiacenta[100001];

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;

        }
        ++prim;
    }
}

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

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

        adaugare(&listadeAdiacenta[x], y);
    }


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

    bfs();

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

    }

    return 0;
}