#include <stdio.h>
#include <vector>

#define MAX_N 100000

using namespace std;

int dist[MAX_N], coada[MAX_N];
vector <int>muchii[MAX_N];

int main() {
    FILE *fin, *fout;
    int n, m, s, a, b, p, u, i;

    fin = fopen( "bfs.in", "r" );
    fscanf( fin, "%d%d%d", &n, &m, &s );
    s--;
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d", &a, &b );
        a--;
        b--;
        muchii[a].push_back( b );
    }
    fclose( fin );

    for ( i = 0; i < m; i++ )
        dist[i] = -1;

    coada[0] = s;
    dist[s] = 0;
    p = u = 0;
    while ( p <= u ) {
        a = coada[p];
        p++;
        for ( i = 0; i < muchii[a].size(); i++ ) {
            if ( dist[muchii[a][i]] == -1 ) {
                u++;
                coada[u] = muchii[a][i];
                dist[muchii[a][i]] = dist[a] + 1;
            }
        }
    }

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

    return 0;
}