#include <vector>
#include <queue>
#include <fstream>

using namespace std;

int main() {
  ifstream f{"bfs.in"};
  ofstream g{"bfs.out"};

  int n, m, s;
  f >> n >> m >> s;
  s--;

  vector<vector<int>> edges(n);

  for (int i = 0; i < m; i++) {
    int ss, dd;
    f >> ss >> dd;
    ss--; dd--;
    edges[ss].push_back(dd);
  }

  queue<int> fringe;
  fringe.push(s);

  vector<int> seen(n, 0);
  vector<int> dist(n, -1);
  dist[s] = 0;

  while (!fringe.empty()) {
    auto p = fringe.front();
    fringe.pop();

    if (seen[p])
      continue;

    seen[p] = 1;

    for (int e : edges[p]) {
      if (!seen[e]) {
        dist[e] = dist[p] + 1;
        fringe.push(e);
      }
    }
  }

  for (int i : dist)
    g << i << " ";
  g << endl;

  return 0;
}