#include <stdio.h>
#define MAXN 1000010

struct twofacedpie
{
	int a, b;	
};

twofacedpie A[MAXN];
int L[MAXN];
int T[MAXN];
int *v[MAXN];
int R[MAXN];
int H[MAXN];
int n,m,S,K=1;


void getstuffs() // and yea i know stuffs is gramatically incorrect (and i probably typo alot in comments)
{
	int i;
	
	scanf("%d%d%d",&n,&m,&S);
	
	for ( i=0; i<m; ++i)
	{
		scanf("%d%d",&A[i].a,&A[i].b);
		T[A[i].a]++;	
	}
	
	for (i=1; i<=n; ++i)
	{
		v[i]= new int [T[i]+3]; v[i][0]=0;
	}
	
	for (i=0; i<m; ++i)
		v[A[i].a][++v[ A[i].a ][0]]=A[i].b;
}

void FFS()
{
	int i,j;
	
	for (i=1; i<=n; ++i)
		R[i]=-1;
	
	L[0]=S; R[S]=0; H[S]=1;
	
	for (i=0; i<K; ++i)
	{
		for (j=1; j<=v[ L[i] ][ 0 ]; ++j)
			if (H[ v[ L[i] ][ j ] ] == 0)
			{
				R[ v[ L[i] ][ j ] ] = R[ L[i] ] +1;
				L[K] =  v[ L[i] ][ j ] ; ++K;
				H[ v[ L[i] ][ j ] ] = 1;
			}		
	}	
}


int main()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	
	getstuffs();
	FFS();
	
	for (int i=1; i<n; ++i)
		printf("%d ",R[i]);
	printf("%d\n",R[n]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}