// librarii
#include <stdio.h>
#include <ctype.h>
	
// constante
#define MAXN 100000
#define MAXM 1000000
#define MAXQ (1024 * 1024)
#define BUFSIZE (128 * 1024)// buffer 128K de citire
#define NIL -1
#define GOL -1
	
// vectori, structuri..
	
// coada
int q[MAXQ];
int p, u;
	
// muchii
int e_list[MAXN];
int e_ptr[MAXM];
int e_next[MAXM];
	
// noduri
int v_val[MAXN];
	
// citire rapida
FILE *fin, *fout;
char rbuf[BUFSIZE];
int rbp = BUFSIZE - 1;
	
// functii
	
// citeste un character cu ajutorul bufferului
int bgetc(){
  if( (rbp = (rbp + 1) & (BUFSIZE - 1)) )
    fread(rbuf, 1, BUFSIZE, fin);
	
  return rbuf[rbp];
}
	
// citeste un numar intreg (POZITIV)
int fgetint(){
  int n = 0, ch;
	
  while( !isdigit(ch = fgetc(fin)) );
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );
	
  return n;
}
	
// adauga in coada
void enqueue( int val ){
  q[u] = val;
  u = (u + 1) & (MAXQ - 1);
}
	
// scoate din coada
void dequeue( int *val ){
  *val = q[p];
  p = (p + 1) & (MAXQ - 1);
}
	
void initqueue(){
  p = u = 0;
}
	
int emptyqueue(){
  return (p == u);
}
	
int main(){
  fin  = fopen("bfs.in",  "r");
  fout = fopen("bfs.out", "w");
	
  int n, m, i, start, a, b;
	
  n = fgetint();
  m = fgetint();
  start = fgetint() - 1;
	
  // construim graful
  for( i = 0 ; i < n ; i++ ){
    e_list[i] = NIL;// initial listele sunt vide
    v_val[i] = GOL;
  }
	
  // adaugam muchiile
  for( i = 0 ; i < m ; i++ ){
    a = fgetint() - 1;
    b = fgetint() - 1;
    
    // adaugam muchia a -> b
    e_ptr[i] = b;
    e_next[i] = e_list[a];
    e_list[a] = i;
  }
	
  // BFS
  initqueue();
  enqueue(start);
  v_val[start] = 0;
  while( !emptyqueue() ){
    dequeue(&a);
    
    i = e_list[a];
    while( i != NIL ){
      b = e_ptr[i];
      if( v_val[b] == GOL ){
        v_val[b] = v_val[a] + 1;
        enqueue(b);
      }
	
      i = e_next[i];
    }
  }
	
  for( i = 0 ; i < n ; i++ )
    fprintf(fout, "%d ", v_val[i]);
	
  fputc('\n', fout);

  fclose(fin);
  fclose(fout);
  return 0;	
}