/* BFS pentru un graf direct
 * Calculeaza distanta de la nodul sursa S la toate nodurile X;
 * daca S nu este conectat cu X, atunci distanta este egala cu -1
 */
#include <bits/stdc++.h>

using namespace std;

struct Node {
  int dist;
  vector<int> adj;
};

Node V[100005];

int N, M, S;

int main() {
#ifndef DEBUG
  freopen("bfs.in", "r", stdin);
  freopen("bfs.out", "w", stdout);
#endif
  cin >> N >> M >> S;
  S--;
  
  for (int i = 0; i < N; i++) {
    V[i].dist = -1;
  }
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    V[a].adj.push_back(b);
  }

  vector<int> q;
  V[S].dist = 0;
  q.push_back(S);

  for (int i = 0; i < (int) q.size(); i++) {
    int k = q[i];
    for (int j = 0; j < (int) V[k].adj.size(); j++) {
      int current = V[k].adj[j];
      if (V[current].dist >= 0) continue;
      V[current].dist = V[k].dist + 1;
      q.push_back(current);
    }

  }
  for (int i = 0; i < N; i++) {
    cout << V[i].dist << " ";
  }
  cout << endl;
}