#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
#define var auto

int main()
{
  std::ifstream in("bfs.in");

  int n, m, s;
  in >> n >> m >> s;

  var graph = new std::vector<int>[n];
  for (var i = 0; i < m; ++i)
  {
    int src, tgt;
    in >> src >> tgt;
    graph[src - 1].push_back(tgt - 1);
  }

  var dst = new int[n];
  for (var i = 0; i < n; ++i)
      dst[i] = INT_MAX;
  dst[--s] = 0;

  std::queue<int> que;
  que.push(s);

  while (!que.empty())
  {
    var crr = que.front();
    que.pop();
    var newdst = dst[crr] + 1;

    for (var adj : graph[crr])
      if (dst[adj] > newdst)
      {
        dst[adj] = newdst;
        que.push(adj);
      }
  }

  std::ofstream out("bfs.out");
  for (var i = 0; i < n; ++i)
    out << (dst[i] == INT_MAX ? -1 : dst[i]) << ' ';
}