#include <stdio.h>

#define Smerenie 1000001
#define Nadejde 100001
#define NIL -1

typedef struct {
  int v, next;
} list;

int N, M, S;
int d[Nadejde];   // d[u] este distanta de la "S" pana la "u".
int adj[Nadejde]; // capetele listelor de adiacenta.
list l[Smerenie]; // lista arcelor alocata static.
int qhead, qtail, Q[Nadejde];

/** Adauga-l pe "v" la lista de adiacenta a lui "u". **/
void addEdge(int u, int v, int pos) {
  l[pos].v = v;
  l[pos].next = adj[u];
  adj[u] = pos;
}

/** Pune in coada nodul "u". **/
void enqueue(int u) {
  Q[qtail++] = u;
}

/** Ia urmatorul nod din coada. **/
void dequeue(int *u) {
  (*u) = Q[qhead++];
}

/** Parcurgerea in latime a grafului. **/
void bfs(int u) {
  int v, pos, dist;
  d[u] = 0;
  enqueue(u);
  do {
    dequeue(&u);
    dist = d[u] + 1;
    /* Probeaza vecinii. */
    for (pos = adj[u]; pos; pos = l[pos].next) {
      v = l[pos].v;
      if (d[v] == NIL) {
        enqueue(v);
        d[v] = dist;
      }
    }
  /* Cat timp coada nu e goala. */
  } while (qhead != qtail);
}

int main(void) {
  int i, u, v;
  FILE *f = fopen("bfs.in", "r");

  /* Citeste graful. */
  fscanf(f, "%d %d %d", &N, &M, &S);
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d", &u, &v);
    addEdge(u, v, i);
  }
  fclose(f);

  f = fopen("bfs.out", "w");

  /* Initializeaza distantele. */
  for (u = 1; u <= N; u++) {
    d[u] = NIL;
  }
  bfs(S);

  for (u = 1; u <= N; u++) {
    fprintf(f, "%d ", d[u]);
  }
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}