#include<fstream>
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<unsigned int> L[100002];
queue<unsigned int> coada;
unsigned int n, s;
int viz[100002];

void Citire()
{
  unsigned int i, x, y, m ;
  ifstream f("bfs.in") ;
  f >> n >> m >> s ;
  for (i = 1; i <= m; i++)
  {
    f>>x>>y ;
    L[x].push_back(y) ;
  }
}

void BFS(int nod_start)
{
  unsigned int i, k, j;
  for(i = 1; i <= n; i++)
    viz[i] = -1;
  coada.push(nod_start);
  viz[nod_start] = 0;

  while (!coada.empty())
  {
    k = coada.front();
    coada.pop();
    for(i=0 ; i<L[k].size() ; i++)
    {
      j = L[k][i];
      if (viz[j] == -1)
      {
        coada.push(j) ;
        viz[j] = viz[k] + 1;
      }
    }
  }
}

void Afisare()
{
    unsigned int i;
    ofstream fout("bfs.out");
    for (i = 1; i <= n; i++)
        fout << viz[i] << " ";
    fout << "\n";
    fout.close();
}

int main()
{
  Citire();
  BFS(s);
  Afisare();
  return 0 ;
}