#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;}