#include<stdio.h>
#include<stdlib.h>

struct GF{
int a,b;
};
GF dst[10000001];
int cnt[100005];
int n,m,s;

int CMP(const void *a,const void *b)
{
	GF x,y;
	x=*(GF *)a;
	y=*(GF *)b;
	if(x.a<y.a)
		return -1;
	if(x.a>y.a)
		return 1;
	if(x.a==y.a)
	{
		if(x.b<y.b)
			return -1;
		if(x.b>y.b)
			return 1;
	}
	return 0;
}
int BINsrc(int val)
{
	
	int mid,st,dr;
	st=0;
	dr=m;
	while(st<dr)
	{
		mid=((st+dr)>>1);
		if(val<=dst[mid].a)
			dr=mid;
		else
			st=mid+1;
	}
	if(dst[dr].a==val)
		return dr;
	else
		return -1;
}
int Q[100005];
void BFS(int s)
{
	//i'll make it DFS cuz i'm tired this evening
	int pos=BINsrc(s),u,p;
	
	u=0;p=1;
	
	int i;
	
	Q[0]=s;cnt[s]=0;
	
	while(u<p)
	{
		i=pos;
		while(dst[i].a==Q[u])
		{
			if(cnt[dst[i].b]<0)
			{
				Q[p++]=dst[i].b;
				cnt[dst[i].b]=cnt[Q[u]]+1;
			}
			++i;
		}
		++u;
		pos=BINsrc(Q[u]);
	}
}
int main()
{
	int i;
	
	
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	
	for(i=1;i<=n;++i)
		cnt[i]=-1;
	
	for(i=0;i<m;++i)
	{
	
		scanf("%d%d",&dst[i].a,&dst[i].b);
		if(dst[i].a==dst[i].b)
		{
			--i;
			--m;
		}
	}
	
	qsort(dst,m,sizeof(dst[0]),CMP);
	
	BFS(s);
	
	for(i=1;i<=n;++i)
		printf("%d ",cnt[i]);
	return 0;
}