#include <stdio.h>

int N, M, S, dist[100005], c[100005], viz[100005];

typedef struct nod
{
	int x;
	nod *a;
} *pNod;
pNod v[100005];

int find(int x, int y)
{
	pNod q;
	for (q = v[x]; q != NULL; q = q -> a) if (q -> x == y) return 1;
	return 0;
}
#define DIM 8192

char ax[DIM+16];
int pz;

inline void cit(int &x)
{
	x=0;
	while((ax[pz]<'0' || ax[pz]>'9') && (ax[pz]!='-'))
		if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;

	
	int neg=0;
	if(ax[pz]=='-')
	{
		neg=1;
		if(++pz==DIM)fread(ax, 1, DIM, stdin),pz=0;
	}
	
	while(ax[pz]>='0' && ax[pz]<='9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz==DIM)fread(ax,1, DIM, stdin),pz=0;
	}
	if(neg) x=-x;
}

void citire()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);

	int i, x, y;
	scanf("%d %d %d",&N,&M,&S);
	for (i = 1; i <= M; i++)
	{
		cit(x); cit(y);
		//scanf("%d %d",&x,&y);
		if (!find(x,y))
		{
			pNod q = new nod;
			q -> x = y;
			q -> a = v[x];
			v[x] = q;
		}
	}
	for (i = 1; i <= N; i++) dist[i] = -1;
	dist[S] = 0;
}

void bfs()
{
	int p, u, poz;
	pNod q;
	p = u = 0;
	c[0] = S; viz[S] = 1;
	while (p <= u)
	{
		poz = p % 100000;
		for (q = v[c[poz]]; q != NULL; q = q -> a)
			if (!viz[q -> x])
			{
				u++;
				c[u % 100000] = q -> x;
				dist[q -> x] = dist[c[poz]] + 1;
				viz[q -> x] = 1;
			}
		p++;
	}
}


int main()
{
	citire();
	bfs();
	for (int i = 1; i <= N; i++) printf("%d ",dist[i]);
	return 0;
}