#include <cstdio>
#define DIM 2000

const int INF = 1<<30;
int a[DIM][DIM], n, m, s, coada[DIM], d[DIM];

int main()
{
	FILE *f = fopen("bfs.in", "r");
	fscanf(f, "%d%d%d", &n, &m, &s);
	int i, x, y, j;
	for (i = 1; i <= n;d[i] = INF,  i++)
		for (j = 1; j <= n; j++)
			a[i][j] = INF;

	for (i = 1; i <= m; i++)
		fscanf(f, "%d%d", &x, &y), a[x][y] = 1;

	fclose(f);
/*
	for (i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			printf("%3d", a[i][j]);

		printf("\n");
	}
*/

	int st, dr;
	st = dr = 1;
	coada[1] = s;
	d[s] = 0;
	while(st <= dr)
	{
		i = coada[st];
		for (j = 1; j <= n; j++)
			if (a[i][j] != INF)
				if (d[i] + 1 < d[j] ) //&& !v[j])
					d[j] = d[i] + 1, coada[++dr] = j;

		st++;
//		v[i] = 1;
	}

	f = fopen("bfs.out", "w");
	for (i = 1; i <= n; i++)
		fprintf(f, "%d ", d[i] == INF? -1 : d[i]);
	fclose(f);

	return 0;
}