#include <stdio.h>
#include <vector>
#include <queue>
#define N 100000

using namespace std;

vector <int> g[N + 1];
int dis[N + 1];
int n;

queue <int> coada;

void bfs( int node ) {
    coada.push( node );
    do {
        node = coada.front();
        coada.pop();
        for ( const int& vecin : g[node] ) {
            if ( dis[vecin] == -1 ) {
                dis[vecin] = dis[node] + 1;
                coada.push( vecin );
            }
        }
    } while ( !coada.empty() );
}

inline void addMuchie( int a, int b ) {
    g[a].push_back( b );
}

int main() {
    FILE *in, *out;
    int m, a, b, start;

    in = fopen( "bfs.in", "r" );
    fscanf( in, "%d%d%d", &n, &m, &start );
    for ( int i = 0; i < m; i ++ ) {
        fscanf( in, "%d%d", &a, &b );
        addMuchie( a, b );
    }

    for ( int i = 1; i <= n; i ++ )
        dis[i] = -1;
    dis[start] = 0;
    bfs( start );

    out = fopen( "bfs.out", "w" );
    fprintf( out, "%d", dis[1] );
    for ( int i = 2; i <= n; i ++ )
        fprintf( out, " %d", dis[i] );
    fprintf( out, "\n" );
    return 0;
}