#include <fstream>
#include <iostream>
#include <cstdio>

using namespace std;

ifstream in("bfs.in");
ofstream out("bfs.out");

struct node{
  int info;
  node* next;

  node(int i, node* n) {
    next = n;
    info = i;
  }
};

int main (int argc, char const *argv[])
{
  int n, m, s;
  in>>n>>m>>s;

  node** graph = new node*[n+1];
  for (int i=0; i<m; ++i) {
    int x, y;
    in>>x>>y;

    node* newnode = new node(y, graph[x]);
    graph[x] = newnode;
  }

  int* solution = new int[n+1];
  for(int i=0;i<=n; ++i) {
    solution[i] = -1;
  }
  int* coada = new int[n+1];

  int head = 0;
  int tail = 1;

  coada[head] = s;
  solution[s] = 0;

  while (head != tail) {
    int nod = coada[head];
    head++;

    node* list = graph[nod];

    while (list) {
      if (solution[list->info] == -1) {
        solution[list->info] = solution[nod] + 1;
        coada[tail++] = list->info;
      }
      list = list->next;
    }
  }
  for(int i=1; i<=n ;++i) {
    cout<<solution[i]<<" ";
  }

  return 0;
}