#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100000
#define MAX_M 1000000
#define none -1

// Liste de adiacenta
int val[MAX_M], next[MAX_M];
int head[MAX_N];

// Coada implementata cu doua stive
int s1[MAX_N], s2[MAX_M];
int s1_size = 0, s2_size = 0;

int dist[MAX_N];

int main() {
    FILE *fin = fopen( "bfs.in", "r" ), *fout = fopen( "bfs.out", "w" );

    int n, m, i, u, v, s;
    fscanf( fin, "%d%d%d", &n, &m, &s );

    for ( i = 0; i < n; i ++ )
        head[i] = dist[i] = none;
    for ( i = 0; i < m; i ++ ) {
        fscanf( fin, "%d%d", &u, &v );
        u --;
        v --;
        val[i] = v;
        next[i] = head[u];
        head[u] = i;
    }

    dist[-- s] = 0;
    s2[s2_size ++] = s;
    while ( s1_size + s2_size > 0 ) {
        if ( s1_size == 0 )
            while ( s2_size > 0 )
                s1[s1_size ++] = s2[-- s2_size];
        u = s1[-- s1_size];

        for ( v = head[u]; v != none; v = next[v] )
            if ( dist[val[v]] == none ) {
                dist[val[v]] = dist[u] + 1;
                s2[s2_size ++] = val[v];
            }
    }

    for ( i = 0; i < n; i ++ )
        fprintf( fout, "%d ", dist[i] );

    fclose( fin );
    fclose( fout );

    return 0;
}