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


int n,m,S,x,y,i,A[100010][1001],C[dim*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++)
{
	fscanf(f,"%d %d",&x,&y);
	A[x][0]++;
		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;
}