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

int main() {
  int N, M, S;
  std::ifstream input("bfs.in");
  input >> N >> M >> S;
  
  std::vector<std::vector<int>> graph;
  std::vector<int> dist;

  graph.resize(N + 1);
  dist.resize(N + 1);
  std::fill(dist.begin(), dist.end(), -1);
  
  int x, y;
  for (int i = 0; i < M; i++) {
    input >> x >> y;
    graph[x].push_back(y);
  }
  
  std::queue<int> q;
  q.push(S);
  dist[S] = 0;
  while (!q.empty()) {
    auto curr = q.front();
    q.pop();
    for (auto& next : graph[curr]) {
      if (dist[next] == -1) {
        q.push(next);
        dist[next] = dist[curr] + 1;
      }
    }
  }

  std::ofstream output("bfs.out");
  for (int i = 1; i <= N; i++) {
    output << dist[i] << ' ';
  }
  output << std::endl;
  return 0;
}