#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <utility>
#include <algorithm>
using namespace std;

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

bitset<100005> vizitat;

bool sortPair (pair<int, int> first,
	       pair<int, int> second)
{
  if (first.first < second.first)
    return true;
  return false;
}

void bfs (int n, int nod, vector<int> *relatii)
{
  vector<pair<int, int> > myHash;
  queue<pair<int, int> > myQueue;
  myQueue.push(make_pair(nod, 0));
  vizitat[nod] = true;

  while (!myQueue.empty())
    {
      pair<int, int> current = myQueue.front(); 
      int nod_curent = current.first;
      int valoare_curenta = current.second;

      myHash.push_back(current);
      
      for (auto &it : relatii[nod_curent])
	if (vizitat[it] == false)
	  myQueue.push (make_pair(it, valoare_curenta + 1)), vizitat[it] = true;

      myQueue.pop();
    }

  if (myHash.size() == 1)
    {
      for (int i = 1; i <= n; ++i)
	if (i != nod)
	  out << -1 << " ";
	else
	  out << 0 << " ";
      return;
    }

  sort (myHash.begin(), myHash.end(), sortPair);
  int i = 1;
  for (vector<pair<int, int> >::iterator it = myHash.begin(); it != myHash.end(); ++it, ++i)
    {
      while (i++ != (*it).first)
	out << -1 << " ";
      --i;

      out << (*it).second << " ";
    }

  while (i != n + 1)
   out << -1 << " ", ++i;
}

int main()
{
  int n; in >> n;
  int m; in >> m;
  int nod_plecare; in >> nod_plecare;

  vector<int> relatii[100005];
  for (int i = 0; i < m; ++i)
    {
      int x, y; in >> x >> y;
      relatii[x].push_back(y);
    }

  bfs (n, nod_plecare, relatii);
}