#include <bits/stdc++.h>

using namespace std;

#define NMAX 100009
#define kInf (1 << 30)

class Task {
public:
  void solve() {
    read_input();
    get_result();
    print_output();
  }

private:
  int n, m, source;;
  vector<int> adj[NMAX];
  vector<int> d;

  void read_input() {
  	ifstream fin("bfs.in");
    fin >> n >> m >> source;
    for (int i = 1; i <= m; ++i) {
      int x, y;
      fin >> x >> y;
      adj[x].push_back(y);
    }
    fin.close();
  }

  void get_result() {
    do_bfs();
  }

  void do_bfs() {
  	d.resize(n + 1);
  	queue<int> Q;
  	for (int i = 1; i <= n; ++i) {
      d[i] = kInf;
    }
    Q.push(source);
    d[source] = 0;
    while (!Q.empty()) {
      int node = Q.front();
      Q.pop();
      for (auto &it : adj[node]) {
        if (d[node] + 1 < d[it]) {
          d[it] = d[node] + 1;
          Q.push(it);
        }
      }
    }
  }

  void print_output() {
  	ofstream fout("bfs.out");
    for (int i = 1; i <= n; ++i) {
   	  if (d[i] == kInf) {
   	  	d[i] = -1;
   	  }
      fout << d[i] << " ";
    }
    fout << "\n";
  	fout.close();
  }
};

int main() {
  Task *task = new Task();
  task->solve();
  delete task;
  return 0;
}