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

using namespace std;

vector<int> graph[MAXN];
int c[MAXNOD + 1],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);
  s--;

  for(i = 0; i < m; i ++){
    fscanf(fin, "%d%d", &a,&b);
    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 < (int)graph[i].size(); j ++)
//      printf("%d ",graph[i][j]);
//    printf("\n");
//  }

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

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

    st ++;
  }

  fout = fopen("bfs.out","w");
  for(i = 0; 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;
//}