#include<cstdio>
#include<cstring>
#include<cstdlib>
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define infile "bfs.in"
#define outfile "bfs.out"
#define nMax 100005
using namespace std;

int Q[nMax], D[nMax];

int *V[nMax], Deg[nMax];

int N, M, SRC;

void read(){
    freopen(infile, "r", stdin);
    scanf("%d %d %d", &N, &M, &SRC);

    int x, y;
    while(M--){
        scanf("%d %d", &x, &y);

        Deg[x] ++;
    }

    FOR(i,1,N){
        V[i] = (int *) malloc((Deg[i] + 1) * sizeof(int));
        Deg[i] = 0;
    }

    rewind(stdin);

    scanf("%d %d %d", &N, &M, &SRC);

    while(M--){
        scanf("%d %d", &x, &y);

        V[x][++ Deg[x]] = y;
    }

    fclose(stdin);
}


void BFS(){
    memset(D, -1, sizeof(D));

    Q[++ Q[0]] = SRC;
    D[SRC] = 0;

    for(int p = 1; p <= Q[0]; ++p){
        int x = Q[p];

        FOR(i,1,Deg[x])
           if(D[V[x][i]] == -1){
               D[V[x][i]] = D[x] + 1;
               Q[++ Q[0]] = V[x][i];
           }
    }
}

void print(){
    freopen(outfile, "w", stdout);

    FOR(i,1,N)
       printf("%d ", D[i]);

    fclose(stdout);
}

int main(){
    read();
    BFS();
    print();

    return 0;
}