#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;

vector < int > vec[MAXN];
queue < int > nod;
int dist[MAXN];
int main () {
    ifstream fin ( "bfs.in" );
    ofstream fout ( "bfs.out" );
    int n , m , s , i , x , y , frq;

    fin >> n >> m >> s;
    for ( i = 0 ; i < m ; i++ ) {
        fin >> x >> y;
        vec[x - 1].push_back ( y - 1 );
    }
    for ( i = 0 ; i < n ; i++ )
        dist[i] = -1;
    nod.push ( s - 1 );
    dist[s - 1] = 0;
    while ( nod.empty () == 0 ) {
        frq = nod.front ();
        nod.pop ();
        for ( i = 0 ; i < vec[frq].size () ; i++ ) {
            if ( dist[vec[frq][i]] == -1 ) {
                nod.push ( vec[frq][i] );
                dist[vec[frq][i]] = dist[frq] + 1;
            }
        }
    }
    for ( i = 0 ; i < n ; i++ )
        fout << dist[i] << ' ';
    fout.put ( '\n' );
    return 0;
}