#include <bits/stdc++.h>
using namespace std;
const int vec_len = 200001;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int n, m, s;
vector<vector<int>> graph(vec_len);
vector<int> dist(vec_len, -1);

int main()
{
  fin >> n >> m >> s;
  for (int i = 1; i <= m; i++)
  {
    int x, y;
    fin >> x >> y;
    graph[x].push_back(y);
  }

  bitset<vec_len> vis;
  queue<int> nodes;

  nodes.push(s);
  dist[s] = 0;
  while (!nodes.empty())
  {
    int curr = nodes.front();
    nodes.pop();

    vis[curr] = true;
    for (int next : graph[curr])
    {
      if (!vis[next])
      {
        dist[next] = dist[curr] + 1;
        vis[next] = true;
        nodes.push(next);
      }
    }
  }

  for (int i = 1; i <= n; i++)
    fout << dist[i] << " ";

  return 0;
}