#include <stdio.h>

#define N 100000
#define M 1000000
#define NIL -1
#define INF -1

struct element {
    int varf, urm;
};

typedef struct element element;

element v[M];
int lst[N+1], d[N+1], nr_v, q[N];

void adauga(int x, int y) {
    v[nr_v].varf = y;
    v[nr_v].urm = lst[x];
    lst[x] = nr_v++;
}

int main() {
    FILE *in, *out;
    in = fopen("bfs.in", "r");
    out = fopen("bfs.out", "w");
    int m, n, x_0;
    fscanf(in, "%d%d%d", &n, &m, &x_0);
    for (int i = 1; i <= n; i++) {
        lst[i] = NIL;
        d[i] = INF;
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        fscanf(in, "%d%d", &x, &y);
        adauga(x, y);
    }
    fclose(in);
    int st = 0, dr = st - 1;
    d[x_0] = 0;
    q[++dr] = x_0;
    while (st <= dr) {
        int x = q[st++];
        for (int p = lst[x]; p != NIL; p = v[p].urm) {
            int y = v[p].varf;
            if (d[y] == INF) {
                d[y] = 1 + d[x];
                q[++dr] = y;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        fprintf(out, "%d ", d[i]);
    }
    fprintf(out, "\n");
    fclose(out);
    return 0;
}