#include<stdio.h>
#define N 100005
#define M 1000005
int n,m,s,d[N],x[M],y[M];
int *a[N];

void alocare()
{
	int i;
	for (i=1;i<=n;++i)
	{
		a[i]=new int[1+d[i]];
		a[i][0]=0;
	}
}

void citire()
{
	int i;
	scanf("%d%d%d",&n,&m,&s);
	for (i=1;i<=m;++i){
		scanf("%d%d",&x[i],&y[i]);
		++d[x[i]];
	}
	alocare();
	for (i=1;i<=m;++i)
		a[x[i]][++a[x[i]][0]]=y[i];
	return;
}

void bfs()
{
	int j,u,p,coada[N],i,x,y;
	for(i=1;i<=n;++i)
		d[i]=-1;
	p=u=0;
	coada[u++]=s;
	d[s]=0;
	while(p!=u)
	{
		x=coada[p++];
		//printf("%d ",coada[p-1]);
		for(j=1;j<=a[x][0];++j)
		{
			y=a[x][j];
			if(d[y]==-1)
			{
				d[y]=1+d[x];
				coada[u++]=y;
				//printf("%d ",coada[u-1]);
			}
		}
	}
	return;
}

void proba()
{
	int i,j;
	for(i=1;i<=n;++i){
		for (j=0;j<=a[i][0];++j)
			printf("%d ",a[i][j]);
		printf("\n");
	}
}
int main()
{
	int i;
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	citire();
//	proba();
	bfs();
	for(i=1;i<=n;++i)
		printf("%d ",d[i]);
	return 0;
}