#include <stdio.h>

#define MAX_N 100000
#define MAX_M 1000000
#define NIL -1

typedef struct {
  int v, next;
} cell;

cell l[MAX_M];
int adj[MAX_N];
int q[MAX_N], qstart, qend;
int dist[MAX_N];

void addEdge(int u, int v, int pos) {
  l[pos].v = v;
  l[pos].next = adj[u];
  adj[u] = pos;
}
void bfs(int nod) {
  q[0] = nod;
  qstart = 0;
  qend = 1;
  dist[nod] = 0;

  while (qstart != qend) {
    int u = q[qstart];
    for (int pos = adj[u]; pos != NIL; pos = l[pos].next) {
      int v = l[pos].v;
      if (dist[v] == NIL) {
        dist[v] = dist[u] + 1;
        q[qend++] = v;
      }
    }
    ++qstart;
  }
}
int main (void) {
  FILE *f;
  int n, m, nod;
  int u, v;

  f = fopen("bfs.in", "r");
  fscanf(f, "%d%d%d", &n, &m, &nod);
  for (int i = 0; i < n; ++i) {
    adj[i] = NIL;
  }
  for (int i = 0; i < m; ++i) {
    fscanf(f, "%d%d", &u, &v);
    addEdge(u - 1, v - 1, i);
  }
  fclose(f);

  for (int i = 0; i < n; ++i) {
    dist[i] = NIL;
  }
  bfs(nod - 1);

  f = fopen("bfs.out", "w");
  for (int i = 0; i < n; ++i) {
    fprintf(f, "%d ", dist[i]);
  }
  fclose(f);
  return 0;
}