#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

const int N = 100001;

vector <int> G [N];
vector <int> vec (N, -1);

void bfs ( int start ){
  queue <int> q;
  int x;
  vec[start] = 0;
  q.push(start);
  while ( !q.empty() ){
    x = q.front();
    q.pop();
    for ( auto i : G[x] )
      if ( vec[i] == -1 ){
        vec[i] = vec[x] + 1;
        q.push( i );
      }
  }
}

int main(){

  int n, m, i, start, x, y;

  //ifstream in ("date.in");
  ifstream in ("bfs.in");
  in >> n >> m >> start;
  for ( i = 0; i < m; i++ ){
    in >> x >> y;
    G[x].push_back(y);
  }
  in.close();

  bfs ( start );

  //ofstream out("date.out");
  ofstream out ("bfs.out");
  for ( i = 1; i <= n; i++ )
    out << vec[i] << " ";
  out.close();

  return 0;
}