#include <cstring>
#include <cstdio>
using namespace std;

int main()
{
    int n, m, s, i, x, y, t, itv, p = 0, u = 0;

    FILE *in = fopen("bfs.in", "r");
    fscanf(in, "%d %d %d", &n, &m, &s);
    int g[n + 1][n], l[n + 1], cost[n + 1], q[n];
    memset(l, 0, sizeof(l));
    memset(cost, -1, sizeof(cost));
    cost[s] = 0;
    q[0] = s;

    for (i = 0; i < m; i++) {
        fscanf(in, "%d %d", &x, &y);
        g[x][l[x]++] = y;
    }
    fclose(in);

    while (u >= p) {
        t = q[p];
        p++;
        for (i = 0; i < l[t]; i++) {
            itv = g[t][i];
            if (cost[itv] == -1) {
                q[++u] = itv;
                cost[itv] = cost[t] + 1;
            }
        }
    }

    FILE *out = fopen("bfs.out", "w");
    for (i = 1; i <= n; i++) {
        fprintf(out, "%d ", cost[i]);
    }
    fclose(out);

    return 0;
}