#include <cstdio>

#define file_in "bfs.in"
#define file_out "bfs.out"

#define nmax 1010000

int n,m,s,i,d[nmax];
int x[nmax];
int y[nmax];

#define CHUNK 8192
char g_buf[CHUNK];
int g_p=CHUNK-1;

inline int get()
{

	int x = 0;
	while (g_buf[g_p] < '0' || g_buf[g_p] > '9')
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;

	while (g_buf[g_p] >= '0' && g_buf[g_p] <= '9')
	{
		x = x*10 + g_buf[g_p]-'0';
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;
	}
	return x;
}

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	n=get();
	m=get();
	s=get();
	for (i=1;i<=m;++i){
		
		x[i]=get();
		y[i]=get();
		if (x[i]==s)
			d[y[i]]=1;		
	}
	
	for (i=1;i<=n;++i)
		 if (i!=s)
			 if (d[i]==0)
				 d[i]=0x3f3f3f3f;
	int ok=0;
	while(!ok){
		
		ok=1;
		for (i=1;i<=m;++i)
			 if (d[y[i]]>d[x[i]]+1)
				 d[y[i]]=d[x[i]]+1,
				 ok=0;
	}
	
	d[s]=0;
	for (i=1;i<=n;++i)
		 if (d[i]==0x3f3f3f3f)
			  printf("-1 ");
		 else
			 printf("%d ", d[i]);
		 
	return 0;

}