#include <cstdio>
#include <cstring>
#include <vector>
#define DIM 100010
using namespace std;

FILE *fin = fopen("bfs.in" ,"r");
FILE *fout= fopen("bfs.out","w");

int Cost[DIM], Frec[DIM], C[DIM], X;
int N, M, S, Y; vector<int> V[DIM];

void SetUp(){
    fscanf(fin, "%d %d %d ", &N, &M, &S);
    memset(Cost, -1, sizeof(Cost));
    for(int i = 1; i <= M; i ++){
        fscanf(fin, "%d %d ", &X, &Y);
        V[X].push_back(Y);
    }
    C[1] = S; Frec[S] = 1; Cost[S] = 0;
    return;
}

void CodeExpert(){
    int u = 1;
    for(int p = 1; p <= u; p ++){
        for(int i = 0; i < V[C[p]].size(); i ++){
            if(Frec[V[C[p]][i]] == 0){
                Frec[V[C[p]][i]] = 1;
                Cost[V[C[p]][i]] = Cost[C[p]] + 1;
                u ++; C[u] = V[C[p]][i];
            }
        }
    }
    return;
}

void Finish(){
    for(int i = 1; i <= N; i ++)
        fprintf(fout, "%d ", Cost[i]);
    return;
}

int main(){
    SetUp();
    CodeExpert();
    Finish();
    fclose(fin);
    fclose(fout);
    return 0;
}