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

ifstream f("bfs.in");
ofstream g("bfs.out");

vector <int> v[100001];
queue <int> q;
int sol[100001];
int n, m, start;
int x, y;

int main(){
  f >> n >> m >> start;
  q.push(start);
  for (int i = 0; i < m; i++){
    f >> x >> y;
    v[x].push_back(y);
  }

  for (int i = 1; i <=n; i++) {
    sol[i] = -1;
  }

  sol[start] = 0;

  while (!q.empty()){
    int nod = q.front();
    for (int i = 0; i < v[nod].size(); i++) {
      if (sol[v[nod][i]] == -1) {
        sol[v[nod][i]] = sol[nod] + 1;
        q.push(v[nod][i]);
      }
    } // for
  q.pop();
  } // while

  for (int i = 1; i <= n; i++) {
    g << sol[i] << " ";
  }
}