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

using namespace std;

int m, n, s;
vector<int> *adj;
vector<int> dist;

int main() {
  ifstream in;
  ofstream out;

  in.open("bfs.in");
  out.open("bfs.out");

  in >> n >> m >> s;
  adj = new vector<int>[n + 1];
  dist.resize(n + 1, -1);

  int x, y;
  for (int i = 0; i < m; ++i) {
    in >> x >> y;

    adj[x].push_back(y);
  }

  dist[s] = 0;
  queue<int> q;

  q.push(s);
  while (!q.empty()) {
    int el = q.front();
    q.pop();

    for (int i = 0; i < adj[el].size(); ++i) {
      if (dist[adj[el][i]] == -1) {
        // not visited
        dist[adj[el][i]] = dist[el] + 1;
        q.push(adj[el][i]);
      }
    }
  }

  // show adj
  // for (int i = 1; i <= n; ++i) {
  //   out << i << " => ";
  //   for (int j = 0; j < adj[i].size(); ++j) {
  //     out << adj[i][j] << " ";
  //   }
  //   out << '\n';
  // }

  // show dist
  for (int i = 1; i <= n; i++)
    out << dist[i] << " ";

  in.close();
  out.close();

  return 0;
}