#include <stdio.h>
#define NMAX 100000
#define MMAX 1000000

int n, m, p, nr, vf[1 + 2 * MMAX], urm[1 + 2 * MMAX], lst[1 + NMAX], viz[1 + NMAX], s, dist[1 + NMAX];
int st, dr;
int stiva[1 + NMAX];

void adauga ( int x, int y ) {
    ++nr;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void bfs () {
    viz[stiva[st]] = 1;
    while (st <= dr) {
        int varf = stiva[st];
        int p = lst[varf];
        int cost = dist[stiva[st]];
        while (p != 0) {
            int y = vf[p];
            if (!viz[y])
                stiva[++dr] = y, dist[y] = cost + 1, viz[y] = 1;
            p = urm[p];
        }
        ++st;
    }
}

int main() {
    int i, x, y;

    FILE *fin = fopen ( "bfs.in", "r" );
    fscanf ( fin, "%d%d%d", &n, &m, &s );
    for ( i = 1; i <= n; ++i )
        dist[i] = -1;
    for ( i = 1; i <= m; ++i ) {
        fscanf ( fin, "%d%d", &x, &y );
        adauga ( x, y );
    }
    fclose ( fin );

    st = dr = 0;
    stiva[0] = s;
    dist[s] = 0;

    bfs ();

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

    return 0;
}