#include <stdio.h>

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

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

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++)
	{
		scanf("%d %d",&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;
	while (p <= u)
	{
		poz = p % 500000;
		for (q = v[c[poz]]; q != NULL; q = q -> a)
			if (dist[q -> x] == -1 || dist[q -> x] > dist[c[poz]] + 1)
			{
				u++;
				c[u % 500000] = q -> x;
				dist[q -> x] = dist[c[poz]] + 1;
			}
		p++;
	}
}


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