#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];

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &n, &m, &s);
	for (i=1;i<=m;++i){
		
		scanf("%d %d", &x[i], &y[i]);
		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;

}