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

#define NMAX 100001

using namespace std;

ifstream fi("bfs.in");
ofstream fo("bfs.out");
int n, m, s, l, c, i, nc, v, d[NMAX];
vector<int> vv[NMAX];
queue<int> q;

int main() {
  fi >> n >> m >> s;
  for (i = 1; i <= m; i++) {
    fi >> l >> c;
    vv[l].push_back(c);
  }
  for (i = 1; i <= n; i++)
    d[i] = -1;
  q.push(s); d[s] = 0;
  while (not q.empty()) {                 /// Cat timp exista elemente in coada,
    nc = q.front();                       /// extragem nodul curent.
    for (i = 0; i < vv[nc].size(); i++) { /// pentru fiecare vecin al nodului curent
      v = vv[nc][i];                      /// Vecinul luat din vector
      if (d[v] == -1) {                   /// este nevizitat?
        q.push(v);                        /// Punem vecinul in coada.
        d[v] = d[nc] + 1;
      }
    }
    q.pop(); /// Scoatem din coada nodul curent.
  }
  for (i = 1; i <= n; i++)
    fo << d[i] << ' ';
  return 0;
}