#include<fstream.h>
#define max 1000000

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

int d[max],n,m,s,c[max];
struct nod {int info;
	    nod *urm;};
nod *l[max];

void citire()
{int i,x,y;
 nod *d;
 fin>>n>>m>>s;
 for(i=1;i<=m;i++)
 {fin>>x>>y;
  d=new nod;
  d->info=y;
  d->urm=l[x];
  l[x]=d;
  }
 }


/*void afisare()
{nod *d;
 for(int i=1;i<=n;i++)
 {d=l[i];
  while(d)
  {fout<<d->info<<" ";
   d=d->urm;
   }
   fout<<"\n";
  }

 }*/

void bfs()
{int i,p,q;
 nod *k;
 d[s]=0;
 c[1]=s;
 p=q=1;

 while(p<=q)
 {i=c[p];
  k=l[i];
  while(k)
  {if(d[k->info]==-1)
   {d[k->info]=d[c[p]]+1;
    q++;c[q]=k->info;
    }
   k=k->urm;
  }

  p++;
  }
 }


int main()
{citire();
 /*afisare();*/

 memset(d,-1,sizeof(d));
 bfs();
 for(int i=1;i<=n;i++)
 fout<<d[i]<<" ";

 fout<<"\n";

 fin.close();
 fout.close();
 return 0;
 }