#include<fstream>
using namespace std;

typedef struct un_nod
{
  int info;
  un_nod*urm;
}*Tnod;

Tnod v[100001];

int cost[100001], coada[100001],n, m,s,i,x,y;

void citire()
{
     Tnod p;
     ifstream f("bfs.in");
        f>>n>>m>>s;
     
     for(i=1;i<=m;i++)
       {
          f>>x>>y;
          p=new un_nod;
          p->info=y;
          p->urm=v[x];
          v[x]=p;
       }
    f.close(); 
 }
 
void bfs(int nod)
{
   int i, j,l;
   
   l=1;
   cost[nod]=1;
   coada[l]=nod;
   
   for(i=1;i<=l;i++)
     for(j=0;j<v[i]->info;j++) 
        if(cost[v[coada[i]]->info]==0)
           {
              coada[++l]=v[coada[i]]->info;
              cost[coada[l]]=cost[coada[i]]+1;
           }
           } 

void afisare()
{
     ofstream g("bfs.out");
     for(i=1;i<=n;i++)
       g<<cost[i]-1<<" ";
       }
       
int main()
{
 citire();
 bfs(s);
 afisare();
 return 0;
  }