#include <stdio.h>
#define MAX_NODURI 100000
#define MAX_MUCHII 1000000

int start[1+MAX_NODURI];
int last[1+MAX_NODURI];
int next[1+MAX_MUCHII];
int muchie[1+MAX_MUCHII];
int best[1+MAX_NODURI];
int queue[MAX_NODURI];
int fQ, lQ;

void push(int val) {
  queue[lQ % MAX_NODURI] = val;
  lQ++;
}

void pop() {
  fQ++;
}

int isEmpty() {
  return fQ == lQ;
}

int getFirst() {
  return queue[fQ % MAX_NODURI];
}

int main() {
  int n, m, a, b, s, i, nod;
  FILE *fin = fopen( "bfs.in" , "r" );
  fscanf(fin, "%d%d%d", &n, &m, &s);
  for(i = 1; i <= m; i++) {
    fscanf(fin, "%d%d", &a, &b);
    if(start[a] == 0)
      start[a] = last[a] = i;
    else
      last[a] = next[last[a]] = i;
    muchie[i] = b;
  }
  fclose( fin );

  for(i = 1; i <= n; i++)
    best[i] = -1;

  best[s] = 0;
  push(s);
  while(!isEmpty()) {
    nod = getFirst();
    pop();
    i = start[nod];
    while(i != 0) {
      if(best[muchie[i]] == -1) {
        push(muchie[i]);
        best[muchie[i]] = best[nod] + 1;
      }
      i = next[i];
    }
  }

  FILE *fout = fopen( "bfs.out" , "w" );
  for(i = 1; i <= n; i++)
    fprintf(fout, "%d ", best[i]);
  fclose( fout );
  return 0;
}