#include <stdio.h>
#define N 100100
#define M 1001000
int *a[N];
int d[N],x[M],y[M],n,m,s;
void Read()
{
	scanf("%d%d%d",&n,&m,&s);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d",&x[i],&y[i]);
		++d[x[i]];
	}
}
void Allocate()
{
	for (int i=1; i<=n; ++i)
	{
		a[i]=new int[1+d[i]];
		a[i][0]=0;
	}
	for (int i=1; i<=m; ++i)
		a[x[i]][++a[x[i]][0]]=y[i];
}
void Bfs()
{
	for (int i=1; i<=n; ++i)
		d[i]=-1;
	int p,u,coada[N],x1,y1;
	p=u=0;
	coada[u++]=s;
	d[s]=0;
	while (p<u)
	{
		x1=coada[p++];
		for (int j=1; j<=a[x1][0]; ++j)
		{
			y1=a[x1][j];
			if (d[y1]==-1)
			{
				coada[u++]=y1;
				d[y1]=1+d[x1];
			}
		}
	}
}
void Print()
{
	for (int i=1; i<=n; i++)
		printf("%d ",d[i]);
	printf("\n");
}
void Solve()
{
	Read();
	Allocate();
	Bfs();
	Print();
}
int main()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	Solve();
}