#include <fstream>
#include <deque>
using namespace std;

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

deque <int> v[100006],coada;
int nrnod,nrmuchii,start,nod1,nod2,nod,nextnod,i;
int sol[100006];
bool ok[100006];


int main()
{
    fi>>nrnod>>nrmuchii>>start;
    for (i=1;i<=nrmuchii;i++)
    {
      fi>>nod1>>nod2;
      v[nod1].push_back(nod2);
    }
    coada.push_back(start);
    ok[start]=true;
    for (i=1;i<=nrnod;i++) sol[i]=-1;
    sol[start]=0;
    while (!coada.empty())
    {
      nod=coada.back();
      coada.pop_back();
      while (!v[nod].empty())
      {
        nextnod=v[nod].back();
        v[nod].pop_back();
        if (!ok[nextnod])
        {
          ok[nextnod]=true;
          coada.push_front(nextnod);
          sol[nextnod]=sol[nod]+1;
        }
      }
    }
    for (i=1;i<=nrnod;i++) fo<<sol[i]<<' ';
    return 0;
}