#include <stdio.h>
#include <string.h>
#include <unistd.h>

#define NMAX 100000
#define MMAX 1000000
#define CHUNK (1 << 24)

static int ve[MMAX+1], ne[MMAX+1];
static char *pbuf, buf[CHUNK], obuf[CHUNK >> 2];
static ssize_t oblen = (CHUNK >> 2) - 1, blen;
static int adj_list[NMAX+1];

static inline int read_int(void)
{
    int x = 0;

    while ('0' <= *pbuf && *pbuf <= '9') {
        x = x * 10 + (*pbuf - '0');
        pbuf++;
    }

    pbuf++;
    return x;
}

static inline void write_int(int x)
{
    if (x == -1) {
        obuf[oblen--] = ' ';
        obuf[oblen--] = '1';
        obuf[oblen--] = '-';
        return;
    }

    obuf[oblen--] = ' ';

    do {
        obuf[oblen--] = '0' + x % 10;
        x /= 10;
    } while (x);
}

int main(void)
{
    int q[NMAX];
    char dist[NMAX+1];
    int n, m, s, i, u, v, qt, qh, new_v;

    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
    blen = read(0, buf, CHUNK);
    pbuf = buf;

    n = read_int();
    m = read_int();
    s = read_int();

    for (i = 1; i <= m; i++) {
        u = read_int();
        v = read_int();

        ve[i] = v;
        ne[i] = adj_list[u];
        adj_list[u] = i;
    }

    memset(dist, -1, sizeof(dist[0]) * (n + 1));

    qt = qh = 0;
    q[qt] = s;
    dist[s] = 0;
    qt++;

    while (qh < qt) {
        i = q[qh];
        qh++;

        for (new_v = adj_list[i]; new_v != 0; new_v = ne[new_v]) {
            if (dist[ve[new_v]] == -1) {
                dist[ve[new_v]] = dist[i] + 1;
                q[qt] = ve[new_v];
                qt++;
            }
        }
    }

    for (i = n; i > 0; i--) {
        write_int(dist[i]);
    }

    write(1, obuf + oblen + 1, (CHUNK >> 2) - oblen - 2);

    return 0;
}