// bfs.cpp : Defines the entry point for the console application.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>

int *e[100001];
int n,m,s;
int c[1000001];
int drum[100001],st=1,dr=1;


void citire()
{
	int x,y;
	
	for(int i=1;i<=n;i++)
	{
		e[i]=(int *)realloc(e[i],sizeof(int));
		e[i][0]=0;
	}

	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		e[x][0]++;
		e[x]=(int *)realloc(e[x],(e[x][0]+1)*sizeof(int));
		e[x][e[x][0]]=y;

	}
}

int main()
{
	int i=0;
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	scanf("%d %d %d",&n,&m,&s);
	citire();
	c[1]=s;

	memset(drum,-1,100001*sizeof(int));
	drum[s]=0;

	while(st<=dr)
	{
		for(int j=1;j<=e[c[st]][0];j++)
			if(drum[e[c[st]][j]]==-1)
			{
				drum[e[c[st]][j]]=drum[c[st]]+1;
				c[++dr]=e[c[st]][j];
			}

		st++;
	}
	for(int i=1;i<=n;i++)
		printf("%d ",drum[i]);


	return 0;
}