#include <iostream>
#include <fstream>

using namespace std;

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

int a[10000][10000], viz[1000], coada[1000], finale[1000];


int main()
{
    int x, y, i, n, m, s, prim, ultim, el;
    f >> n >> m >> s;

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

    for(i = 1; i <= n; i++){
        finale[i] = -1;
    }

    prim = 1;
    ultim = 1;

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

    while(prim <= ultim){
            el = coada[prim];
        for(i = 1; i <= n; i++){
            if(a[el][i] == 1 && viz[i] == 0){
                viz[i] = 1;
                ultim++;
                coada[ultim] = i;
                finale[i] = finale[el] + 1;
            }
        }
        prim++;
    }

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

    return 0;
}