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

ifstream cin("bfs.in");
ofstream cout("bfs.out");

int n, m, s;
vector<vector<int>> G;
vector<int> C;
vector<bool> VC;

void bfs(int k) {
  C[k] = 0;
  VC[k] = 1;
  
  queue<int> Q;
  Q.push(k);
  
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    
    for (auto y : G[x])
      if (VC[y] == 0) {
        C[y] = C[x] + 1;
        VC[y] = 1;
        Q.push(y);
      }
  }
}

int main() {
  cin >> n >> m >> s;
  
  G = vector<vector<int>> (n + 1);
  C = vector<int> (n + 1, -1);
  VC = vector<bool> (n + 1, 0);
  
  for (int i = 1, a, b; i <= m; ++i)
    cin >> a >> b, G[a].push_back(b);
  
  bfs(s);

  for (int i = 1; i <= n; ++i)
    cout << C[i] << " ";

  cin.close();
  cout.close();
  return 0;
}