#include<fstream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

const int MMAX = 1000000;

vector< vector<int> > G(MMAX);
queue<int> Q;
int Cost[MMAX], L[MMAX], N, M, St;

void read(){
  ifstream fin("bfs.in");
  fin >> N >> M >> St;
  for(int i = 0, x, y; i < M; i++){
    fin >> x >> y;
    G[x-1].push_back(y-1);
    L[x-1]++;
  }
  fin.close();
}

void BFS(int node){
  memset(Cost, -1, sizeof(Cost));
  int top;

  Q.push(node);
  Cost[node] = 0;
  while(Q.empty() == false){
    top = Q.front();
    Q.pop();
    for(int i = 0; i < L[top]; i++){
      if(Cost[G[top][i]] == -1){
        Q.push(G[top][i]);
        Cost[G[top][i]] = Cost[top] + 1;
      }
    }
  }
}

void write(){
  ofstream fout("bfs.out");
  for(int i = 0; i < N; i++){
    fout << Cost[i] << " ";
  }
  fout.close();
}

int main(){
  read();
  BFS(St-1);
  write();
  return 0;
}