#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
using namespace std;
#define mp make_pair
#define fs first
#define sc second
int n,m,s;
int v[100010];
int *a[100010];
int cat[100010];
void citire()
{
	scanf("%d%d%d",&n,&m,&s);
	int x,y;
	for(; m; m--)
	{
		scanf("%d%d",&x,&y);
		if((cat[x]&7)==0)
			a[x]=(int*)realloc(a[x],(cat[x]+10)*sizeof(int));
		a[x][cat[x]++]=y;
	}
}
void bfs()
{
	queue < pair<int,int> > q;
	q.push(mp(s,0));
	int i;
	pair<int,int> x;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(i=0; i<cat[x.fs]; i++)
		{
			if(v[a[x.fs][i]]==-1)
			{
				v[a[x.fs][i]]=x.sc+1;
				q.push(mp(a[x.fs][i],x.sc+1));
			}
		}
	}
}
int main()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	citire();
	for(int i=1; i<=n; i++)
		v[i]=-1;
	bfs();
	v[s]=0;
	for(int i=1; i<n; i++)
		printf("%d ",v[i]);
	printf("%d\n",v[n]);
	return 0;
}