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

#define N 100000
int l[N + 1], cost[N + 1], q[N];
vector<int> g[N + 1];

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

    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].push_back(y);
    }
    fclose(in);

    for (i = 1; i <= n; i++) {
        l[i] = g[i].size();
    }

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