#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;

struct Edge {
    int v, next;
};

Edge l[MAX_M];
int adj[MAX_N];
int d[MAX_N];

inline char getChar() {
    static char buff[BUFFSIZE];
    static int pos = BUFFSIZE;
    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() - 1;

    for (int i = 0; i < N; i++) {
        adj[i] = NIL;
        d[i] = NIL;
    }
    for (int i = 0; i < M; i++) {
        u = readInt() - 1; v = readInt() - 1;
        l[i].v = v;
        l[i].next = adj[u];
        adj[u] = i;
    }

    d[startNode] = 0;
    Q[qEnd++] = startNode;
    while (qStart != qEnd) {
        u = Q[qStart++];
        for (int i = adj[u]; i != NIL; i = l[i].next) {
            v = l[i].v;
            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;
}