#include<stdio.h>
#include<stdlib.h>
#define INF 1000005
struct Point{
int x,y;
};
Point Graf[INF];
int n,m,s,VF[INF],cost[INF],q[INF];
void lee(int s)
{
	int u,p,i,last;
	u=0;
	p=1;
	cost[s]=0;
	q[u]=s;
	while(u<=p)
	{
		//merg pe vecinii nodului curent
		i=VF[q[u]];
		last=Graf[i].x;
		while(Graf[i].x==last)
		{
			if(Graf[i].x!=Graf[i].y)
			{
				if(cost[Graf[i].y]==INF)
					q[p++]=Graf[i].y;
				if(cost[Graf[i].y]>cost[Graf[i].x]+1)
					cost[Graf[i].y]=cost[Graf[i].x]+1;
			}
			++i;
		}
		++u;
	}
}
int cmp(const void *a,const void *b)
{
	int x,y;
	x=*(int *)a;
	y=*(int *)b;
	if(x>y)
		return 1;
	if(x<y)
		return -1;
	if(x==y)
		return 0;
}
int main()
{
	int i,nr=0;
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	for(i=0;i<m;++i)
	{
		scanf("%d%d",&Graf[i].x,&Graf[i].y);
		cost[i]=INF;
	}
	qsort(Graf,m,sizeof(Graf[0]),cmp);
	int last=Graf[0].x;
	VF[Graf[0].x]=0;
	nr=1;
	for(i=1;i<m;++i)
	{
		while(Graf[i].x==last)++i;
		VF[Graf[i].x]=i;
		++nr;
		last=Graf[i].x;
	}
	lee(s);
	for(i=1;i<=nr;++i)
	{
		if(cost[i]==INF)
			printf("-1 ");
		else
			printf("%d ",cost[i]);
	}
	return 0;
}