#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int p,u,n,m,s,i,nr,ap[100002],c[100002],in[100002];
struct str
{
	int x,y;
};
bool cmp(str a,str b)
{
	return a.x<b.x;
}
str a[2000002];
int main()
{
freopen("bfs.in","r",stdin);
freopen("bfs.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&s);
for(i=1;i<=m;i++)
{
	nr++;
	scanf("%d",&a[nr].x);
	scanf("%d",&a[nr].y);
}
sort(a+1,a+nr+1,cmp);
for(i=1;i<=nr;i++)
	if(a[i].x!=a[i-1].x) in[a[i].x]=i;
p=1;
u=1;
c[p]=s;
memset(ap,-1,sizeof(ap));
ap[s]=0;
while(p<=u)
{
	for(i=in[c[p]];i<=nr;i++)
	{
		if(a[i].x!=c[p]) break;
		if(ap[a[i].y]==-1)
		{
			u++;
			ap[a[i].y]=ap[c[p]]+1;
			c[u]=a[i].y;
		}
	}
	p++;
}
for(i=1;i<=n;i++)
	printf("%d ",ap[i]);
return 0;
}