#include<fstream.h>
#define max 100000
 ifstream f("bfs.in");
 ofstream g("bfs.out");
   long ok,cont,p,val[max],uz[max],vec[max],n,m,s,i,x,y;

typedef struct nod
{
 int info;
 nod *urm;
} *pNod;


pNod a[max];


void add(pNod &prim,int val)
{
 pNod x;
 x=new nod;
 x->info=val;
 x->urm=prim;
 prim=x;
}



int main()
{
  f>>n>>m>>s;
 for(i=1;i<=m;i++)
  f>>x>>y,add(a[x],y);
 ok=1;
 cont=1;
 vec[1]=s;
 p=1;
 uz[vec[1]]=1;
 for(i=1;i<=p;i++)
 {
  pNod prim=a[vec[i]];
  while(prim)
  {
   if(uz[prim->info]==0)
   {
    vec[++p]=prim->info;
    val[vec[p]]=cont;
    uz[vec[p]]=1;
   }
   prim=prim->urm;
  }
  cont++;
 }
 for(i=1;i<=n;i++)
  if(val[i]==0&&i!=s) g<<-1<<" ";
   else g<<val[i]<<" ";

  return 0;
}