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

void queue_push( int x ) {
    s2[s2_size ++] = x;
}

int queue_pop() {
    if ( s1_size == 0 )
        while ( s2_size > 0 )
            s1[s1_size ++] = s2[-- s2_size];
    return s1[-- s1_size];
}

int queue_size() {
    return s1_size + s2_size;
}

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;
    queue_push( s );
    while ( queue_size() > 0 ) {
        u = queue_pop();
        for ( v = head[u]; v != none; v = next[v] )
            if ( dist[val[v]] == none ) {
                dist[val[v]] = dist[u] + 1;
                queue_push( val[v] );
            }
    }

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

    fclose( fin );
    fclose( fout );

    return 0;
}