// librarii
#include <stdio.h>
#include <ctype.h>

// constante
#define MAXN 100000
#define MAXM 1000000
#define MAXQ (128 * 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[MAXN];

// 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;
}