#include <cstdio>
using namespace std;
long n,m,k,i,xd,xa,poz,start,stop,d;
long st[100001],sf[100001],next[1000001],nod[1000001],stiv[1000001],dist[100001];
int main()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	scanf("%ld%ld%ld",&n,&m,&k);
	for(i=1;i<=m;i++){
		scanf("%ld%ld",&xd,&xa);
		if(xd!=xa){
			if(sf[xd]==0){poz=i;st[xd]=i;}
			else{poz=sf[xd];}
			next[poz]=i;
			nod[i]=xa;
			next[i]=0;
			sf[xd]=i;
				   }
					 }
	stiv[1]=k;dist[k]=1;start=1;stop=1;
	while(start<=stop){
		i=st[stiv[start]];
		d=dist[stiv[start]]+1;
		while(i){
			if(dist[nod[i]]==0){
				dist[nod[i]]=d;stiv[++stop]=nod[i];
							   }
			i=next[i];
				}
		start++;
					  }
	for(i=1;i<=n;i++){printf("%ld ",dist[i]-1);}
return 0;
}