#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define dim  1000010


int n,m,S,x,y,i,*A[dim],C[dim],B[dim];
void citire()
{ FILE *f=fopen("bfs.in","r");
	fscanf(f,"%d %d %d",&n,&m,&S);
	for(i=1;i<=m;i++)
	{
	A[i]=(int *) realloc(A[i],sizeof(int));
		A[i][0]=0;
	}
	
for(i=1;i<=m+1;i++)
{
	fscanf(f,"%d %d",&x,&y);

	A[x][0]++;
	A[x]=(int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
	A[x][A[x][0]]=y;
	
		
	
}	
fclose(f);
}

void BFS(int x)
{
	int i,in,sf,k;
	
	
	memset(B,-1,sizeof(B));
	
	 B[x]=0;
	C[0]=x; in=sf=0;
	k=0;
	while(in<=sf)
	{
		x=C[in++];
		for(i=1;i<=A[x][0];i++)
			if(B[A[x][i]]==-1)
			{
			B[ A[x][i] ]=B[x]+1;
			
			C[++sf]=A[x][i];
			
			}
		
		
	}
	
	

}

void afisare()
{
	FILE *g=fopen("bfs.out","w");
for(i=1;i<=n;i++)
	fprintf(g,"%d ",B[i]);
fprintf(g,"\n");


fclose(g);


}


int main()
{

citire();
BFS(S);
afisare();

return 0;
}