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

using namespace std;
ifstream in ("bfs.in");
ofstream out ("bfs.out");

const int MAXN = 100010;

int n,m,s;
vector <bool> V (MAXN);
vector <int> D (MAXN);
vector<int> L[MAXN]; //L[i] -- vectorul care contine vecinii lui i

void BFS()
{
  queue<int> Q;
  for (int i = 0; i< n; i++){
    D[i] = -1;
  }
  D[s] = 0;
  Q.push(s);

  while (!Q.empty()){
    int current = Q.front();
    V[current] = 1;
    for (auto next: L[current]) {
      if (!V[next]){
        Q.push(next);
        V[next] = 1;
        D[next] = D[current] + 1;
        }
    }
    Q.pop();
    }
}

int main()
{
  	in >> n >> m >> s;
  	for (int i = 0; i < m; i++){
      int from, to;
      in >> from >> to;
      L[from].push_back(to);
  	}
    BFS();
    for (int i = 1; i <= n; i++){
        out << D[i] << " ";
    }
    return 0;
}