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

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

queue <int> v[50006],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(nod2);
    }
    coada.push(start);
    ok[start]=true;
    for (i=1;i<=nrnod;i++) sol[i]=-1;
    sol[start]=0;
    while (!coada.empty())
    {
      nod=coada.front();
      coada.pop();
      while (!v[nod].empty())
      {
        nextnod=v[nod].front();
        v[nod].pop();
        if (!ok[nextnod])
        {
          ok[nextnod]=true;
          coada.push(nextnod);
          sol[nextnod]=sol[nod]+1;
        }
      }
    }
    for (i=1;i<=nrnod;i++) fo<<sol[i]<<' ';
    return 0;
}