#include <bits/stdc++.h>

using namespace std;
ifstream fin ("bfs.in");
ofstream fout ("bfs.out");
int a[1001][1001], vizitat[1001], q[1001], distanta[1001];
int
main ()
{
  int n, m, start;
  fin >> n >> m >> start;
  for (int i = 1; i <= m; ++i)
    {
      int x, y;
      fin >> x >> y;
      cout << x;
      a[x][y] = 1;
    }
  memset (distanta, -1, sizeof (distanta));
  int st, dr;
  st = dr = 1;
  q[st] = start;
  vizitat[start] = 1;
  distanta[start] = 0;
  while (st <= dr)
    {
      int k = q[st];
      for (int i = 1; i <= n; ++i)
	{
	  if (a[k][i] == 1 && vizitat[i] == 0)
	    {
	      dr++;
	      vizitat[i] = 1;
	      q[dr] = i;
	      distanta[i] = distanta[k] + 1;
	    }
	}
      st++;
    }
  for (int i = 1; i <= n; ++i)
    fout << distanta[i] << " ";

  return 0;
}