#include <bits/stdc++.h>

const int MAX_N = 100000;
const int MAX_M = 1000000;
const int BUFFSIZE = 65536;
const int NIL = -1;

int Q[MAX_N], qStart, qEnd;

int *adj[MAX_N];
int deg[MAX_N];
int d[MAX_N];

char buff[BUFFSIZE];
int pos = BUFFSIZE;

inline char getChar() {
    if (pos == BUFFSIZE) {
        fread(buff, 1, BUFFSIZE, stdin);
        pos = 0;
    }
    return buff[pos++];
}

inline int readInt() {
    int q = 0;
    char c;
    do {
        c = getChar();
    } while (!isdigit(c));
    do {
        q = (10 * q) + (c - '0');
        c = getChar();
    } while (isdigit(c));
    return q;
}

int main(void) {
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
    int N, M, startNode;
    int u, v;

    N = readInt(); M = readInt(); startNode = readInt();
    for (int i = 0; i < M; i++) {
        u = readInt() - 1; v = readInt();
        deg[u]++;
    }
    fseek(stdin, 0, SEEK_SET);
    pos = BUFFSIZE;

    for (int i = 0; i < N; i++) {
        adj[i] = (int *) malloc(deg[i] << 2);
        deg[i] = 0;
        d[i] = NIL;
    }

    N = readInt(); M = readInt(); startNode = readInt() - 1;
    for (int i = 0; i < M; i++) {
        u = readInt() - 1; v = readInt() - 1;
        adj[u][deg[u]++] = v;
    }

    d[startNode] = 0;
    Q[qEnd++] = startNode;
    while (qStart != qEnd) {
        u = Q[qStart++];
        for (int i = 0; i < deg[u]; i++) {
            v = adj[u][i];
            if (d[v] == NIL) {
                d[v] = d[u] + 1;
                Q[qEnd++] = v;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        printf("%d ", d[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}