#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");
int m, n, s;
vector<vector<int>> lista;
queue<int> coada;
vector<int> viz;
vector<int> d;
vector<int> tata;

void BFS(int s) {
  coada.push(s);
  viz[s] = 1;
  d[s] = 0;
  while (!coada.empty()) {
    int i = coada.front();
    coada.pop();
    cout << i << "\n";
    for (auto &j : lista[i]) {
      if (viz[j] == 0) {
        coada.push(j);
        viz[j] = 1;
        tata[j] = i;
        d[j] = d[i] + 1;
      }
    }
  }
}

int main() {
  f >> n >> m >> s;
  int x1, x2;
  lista.resize(n + 1);
  viz.resize(n + 1);
  d.resize(n + 1, 0);
  tata.resize(n + 1, -1);

  for (int i = 1; i <= m; i++) {
    f >> x1 >> x2;
    lista[x1].push_back(x2);
    /*lista[x2].push_back(x1);*/
  }
  BFS(s);

  for (int i = 1; i <= n; i++) {

    if (i == s) {
      g << 0 << ' ';
    } else if (i != s) {
      if (d[i] != 0) {
        g << d[i] << ' ';
      } else {
        g << -1 << ' ';
      }
    }
  }

  f.close();
  g.close();

  return 0;
}