#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
#define mMax 1000005
using namespace std;

int Q[nMax], D[nMax];

int *edge[2];

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

int N, M, SRC;

void read(){
    freopen(infile, "r", stdin);

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

    SRC --;
    edge[0] = (int *) malloc((M + 1) * sizeof(int));
    edge[1] = (int *) malloc((M + 1) * sizeof(int));

    FOR(i,1,M){
        scanf("%d %d", edge[0] + i, edge[1] + i);

        edge[0][i] --;
        edge[1][i] --;

        Deg[edge[0][i]] ++;
    }

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

    FOR(i,1,M)
        V[edge[0][i]][Deg[edge[0][i]] ++] = edge[1][i];

    free(edge[0]);
    free(edge[1]);

    fclose(stdin);
}


void BFS(){
    memset(D, -1, sizeof(D));
    int l, r, *p;

    D[Q[l = r = 1] = SRC] = 0;

    for(; l <= r; ++l){
        for(p = V[Q[l]]; *p != -1; p ++)
           if(D[*p] == -1)
               D[Q[++r] = *p] = D[Q[l]] + 1;
    }
}

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

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

    fclose(stdout);
}

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

    return 0;
}