// https://infoarena.ro/problema/bfs
#include <bits/stdc++.h>
#include <deque>
using namespace std;

#ifdef INFOARENA
ifstream fin("bfs.in");
ofstream fout("bfs.out");
#define cin fin
#define cout fout
#endif

int main() {
  int n; cin >> n;
  int m; cin >> m;

  int source; cin >> source;

  vector<vector<int>> graph;
  graph.resize(n + 1);
  for (int i = 0; i < m; i++) {
    int a; int b;
    cin >> a >> b;
    graph[a].push_back(b);
  }

  // cout << source << ' ' << n << ' ' << m << '\n';
  // for (int i = 1; i <= n; i++) {
  //     cout << i << ": ";
  //     for (int neighbor : graph[i]) {
  //         cout << neighbor << " ";
  //     }
  //     cout << "\n";
  // }

  vector<int> distances;
  distances.resize(n + 1, -1);
  distances[source] = 0;

  deque<int> dq;
  dq.push_back(source);

  while (!dq.empty()) {
    int node = dq.front(); dq.pop_front();

    for (auto neigh : graph[node]) {
      if (distances[neigh] != -1) continue;
      distances[neigh] = distances[node] + 1;
      dq.push_back(neigh);
    }
  }

  for (int i = 1; i <= n; i++)
    cout << distances[i] << ' ';


  return 0;
}