#include <iostream>
#include <fstream>

using namespace std;

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

int a[1000][1000], viz[1000001], finale[1000001], N, M, S, i, j, x, y, ultim, el, coada[1000001];



int main()
{
    int andi = 1;
    f >> N >> M >> S;

    for(i = 1; i <= M; i++){
        f >> x >> y;
        a[x][y] = 1;
    }

    for(i = 1; i <= N; i++){
        viz[i] = 0;
    }

    viz[S] = 1;
    coada[1] = S;
    ultim = 1;

    for(i = 1; i <= N; i++){
        bool executed = false;
        el = coada[i];
        for(j = 1; j <= N; j++){
            if(a[el][j] == 1 && viz[j] == 0){
                executed = true;
                ultim++;
                coada[ultim] = j;
                viz[j] = 1;
                finale[j] = andi;
        }
    }
    if(executed){
        andi++;}
}

    finale[S] = 0;

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

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

 return 0;
}