#include <stdio.h>

#define dmax 1000005
#define Dmax 100005

int vf[dmax];
int urm[dmax];
int lst[Dmax];
int nr;

int C[Dmax];

int d[Dmax];

int N, M;

void adauga(int x, int y)
{
	//ADAUGA IN LISTA LUI x PE y

	nr++;
	vf[nr] = y;
	urm[nr] = lst[x];
	lst[x] = nr;
}

int main()
{
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);

	int i, x, y, p;
	int S;

	scanf("%d %d", &N, &M);

	scanf("%d", &S);

	for(i = 1; i <= M; i++)
	{
		scanf("%d %d", &x, &y);

		adauga(x, y);
	}

	for(i = 1; i <= N; i++)
	{
		d[i] = -1;
	}

	int first, last;

	C[1] = S;
	d[S] = 0;

	first = last = 1;

	while(first <= last)
	{
		x = C[first];

		// PARCURG VECINII y AI LUI x

		p = lst[x];

		while(p)
		{
			y = vf[p];

			if(d[y] == -1)
			{
				C[++last] = y;

				d[y] = 1 + d[x];
			}

			p = urm[p];
		}

		first++;
	}

	for(i = 1; i <= N; i++)
	{
		printf("%d ", d[i]);
	}

	return 0;
}