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

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

static struct vlist {
    int v;
    struct vlist *next;
} *adj_list[NMAX+1], edges[MMAX];

static char buf[CHUNK], obuf[CHUNK >> 2];
static ssize_t blen, oblen = (CHUNK >> 2) - 1, bpos = CHUNK;

static inline int read_int(int end)
{
    int x = 0, sgn = 1;

    while (1) {
        if (bpos == CHUNK) {
            blen = read(0, buf, CHUNK);
            bpos = 0;
        }

        if (buf[bpos] == '-') {
            sgn = -1;
        } else if ('0' <= buf[bpos] && buf[bpos] <= '9') {
            x = x * 10 + (buf[bpos] - '0');
        } else if (buf[bpos] == end) {
            bpos++;
            return sgn * x;
        }

        bpos++;
    }
}

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];
    struct vlist *new_v;
    int n, m, s, i, u, v, qt, qh;

    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);

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

    for (i = 0; i < m; i++) {
        u = read_int(' ');
        v = read_int('\n');

        new_v = edges + i;
        new_v->v = v;
        new_v->next = adj_list[u];
        adj_list[u] = new_v;
    }

    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 != NULL; new_v = new_v->next) {
            if (dist[new_v->v] == -1) {
                dist[new_v->v] = dist[i] + 1;
                q[qt] = new_v->v;
                qt++;
            }
        }
    }

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

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

    return 0;
}