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


int n,m,S,x,y,i,A[dim][dim],viz[dim],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,j,I,J;
	
	
	memset(B,-1,sizeof(B));
	
	viz[x]=1; B[x]=0;
	C[0]=x; in=sf=0;
	k=0;
	while(in<=sf)
	{k++; I=in; J=sf;
	for(j=I;j<=J;j++)
		{
		x=C[in++];
		for(i=1;i<=A[x][0];i++)
			if(!viz[A[x][i]])
			{
			B[ A[x][i] ]=k;
			
			viz[A[x][i]]=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;
}