#include<stdio.h> 
#include<stdlib.h> 
FILE *f,*g; 

int s,x,y,i,p=1,u=1,coada[100001],*v[100001],sel[100001],n,m,niv[1000001]; 
int main()  
{ 
f=fopen("bfs.in","r"); 
fscanf(f,"%d%d%d",&n,&m,&s); 
for(i=1;i<=n;i++)  
{ 
v[i]=(int*)realloc(v[i],sizeof(int)); 
v[i][0]=0; 
} 
for(i=1;i<=m;i++) 
{ 
fscanf(f,"%d%d",&x,&y); 
v[x][0]++; 
v[x]=(int*)realloc(v[x],(v[x][0]+1)*sizeof(int)); 
v[x][v[x][0]]=y; 
} 
fclose(f); 
coada[1]=s; 
sel[s]=1; 
while(p<=u)  
{ 
for(i=1;i<=v[coada[p]][0];i++) 
if(sel[v[coada[p]][i]]==0)
{ 
u++; 
coada[u]=v[coada[p]][i];
sel[coada[u]]=1; 
niv[coada[u]]=niv[coada[p]]+1; 
} 
p++; 
} 
for(i=1;i<=n;i++) 
if(niv[i]==0) niv[i]=-1; 
niv[s]=0; 
g=fopen("bfs.out","w"); 
for(i=1;i<=n;i++) 
fprintf(g,"%d ",niv[i]); 
fprintf(g,"\n"); 
fclose(g); 
return 0;}