#include <deque>
#include <iostream>
#include <vector>

typedef unsigned int ll;

using namespace std;

int main() {
  freopen("bfs.in", "r", stdin);
  freopen("bfs.out", "w", stdout);
  ios::sync_with_stdio(0);

  ll n, m, source;

  cin >> n >> m >> source;
  vector<vector<bool>> matrix(n + 1, vector<bool>(n + 1, false));

  for (ll i = 0; i < m; ++i) {
    ll a, b;
    cin >> a >> b;
    matrix[a][b] = true;
  }

  deque<pair<ll, ll>> q;
  vector<bool> visited(n + 1, false);
  vector<ll> solve(n + 1, -1);

  q.push_back({source, 0});
  visited[source] = true;

  ll distance = 0;
  while (!q.empty()) {
    pair<ll, ll> current = q.front();
    solve[current.first] = current.second;
    q.pop_front();

    for (ll i = 1; i <= n; ++i) {
      if (matrix[current.first][i] == true && visited[i] == false) {
        visited[i] = true;
        q.push_back({i, current.second + 1});
      }
    }
  }

  for (ll i = 1; i < solve.size(); ++i) {
    cout << solve[i] << " ";
  }
  return 0;
}