#include <fstream.h>
#include <queue>
using namespace std;

#define nmax (100005)

int N, M, S;
int *G[nmax], Viz[nmax];
queue<int> Q;

// read data
void read() {


    // read graph size
    ifstream fin("bfs.in");
    fin >> N >> M >> S;

    // prepare lists
    for (int i = 1; i <= N; ++i) {
        G[i] = (int*) malloc(sizeof (int));
        G[i][0] = 0;
    }

    // read degrees
    while (M--) {
        int x, y;
        fin >> x >> y;
        G[x][0]++;
    }
    fin.close();

    // prepare lists for incoming degrees
    for (int i = 1; i <= N; ++i) {
        G[i] = (int*)realloc(G[i], (G[i][0] + 1) * sizeof(int));
        G[i][0] = 0;
    }

    // read actual vertices
    ifstream fim("bfs.in");
    fim >> N >> M >> S;
    while (M--) {
        int x, y;
        fim >> x >> y;
        G[x][++G[x][0]] = y;
    }
    fim.close();

}

// solve task
void solve() {

    // set all to -1
    for (int i = 1; i <= N; ++i) {
        if (i != S) {
            Viz[i] = -1;
        }
    }

    // do queue operation
    for (Q.push(S); !Q.empty(); Q.pop()) {
        int v = Q.front();
        for (int i = 1; i <= G[v][0]; ++i) {
            int w = G[v][i];
            if (Viz[w] < 0) {
                Viz[w] = 1+Viz[v];
                Q.push(w);
            }
        }
    }
    
}

// write data
void write() {

    // write array
    ofstream fout("bfs.out");
    for (int i = 1; i <= N; ++i) {
        fout << Viz[i] << ' ';
    }
    fout << '\n';
    fout.close();

}

int main() {

    read();
    solve();
    write();
    return 0;

}