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

using namespace std;

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

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

  std::cout << n << " " << m << " " << s << std::endl;

  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[e] == -1 ? dist[p] + 1 : min(dist[e], dist[p] + 1);
        fringe.push(e);
      }
    }
  }

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

  return 0;
}