#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[i].push_back(tgt);
  }

  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] << ' ';
}