#include <iostream>
#include <vector>
#include <stdio.h>
#define MAXN 100000
#define MAXNOD 1000000

using namespace std;

vector<int> graph[MAXN];
int c[MAXNOD],d[MAXNOD];

int main(){
  int n,m,s,i,a,b,st,dr,gr;
  FILE *fin, *fout;

  fin = fopen("bfs.in","r");
  fscanf(fin, "%d%d%d",&n,&m,&s);

  for(i = 0; i < m; i ++){
    fscanf(fin, "%d%d", &a,&b);
    graph[a].push_back(b);
  }
  fclose(fin);

  //printf("%d",graph[1][0]);

  st = 0;
  dr = 1;
  c[0] = s;

//  for(i = 0; i < n; i ++){
//    for(int j = 0; j < graph[i].size(); j ++)
//      printf("%d ",graph[i][j]);
//    printf("\n");
//  }

  d[s] = 1;
  while(st < dr){
    for(i = 0; i < graph[c[st]].size(); i ++){
      gr = graph[c[st]][i];

      if(d[gr] > d[st] + 1 || d[gr] == 0){
        d[gr] = d[c[st]] + 1;
        c[dr] = gr;
        dr++;
      }
    }

    st ++;
  }

  fout = fopen("bfs.out","w");
  for(i = 1; i <= n; i ++){
    fprintf(fout, "%d ",d[i] - 1);
  }
  fprintf(fout, "\n");
  fclose(fout);

  return 0;
}

//#include <iostream>
//#include <vector>
//#include <stdio.h>
//#define MAXN 100
//
//using namespace std;
//
//vector<int> graph[MAXN];
//
//int main(){
//  int i,n = 0;
//  for(i = 0; i < 47; i ++){
//    printf("%d : %d\n",i,n);
//    n = n*2 + 1;
//    n %= 47;
//  }
//  return 0;
//}