#include <stdio.h>
#include <conio.h>


int **aloca(int n)
{
	int **a;
	a = new int*[n];
	for (int i = 0; i < n; i++)
		a[i] = new int[n];
	return a;
}

int ins_coada(int *coada, int n, int s, int *p, int *k)
{
	p[s] = (*k);
	coada[n] = s;
	return ++n;
}

int excl_coada(int *coada, int n, int *s, int *k)
{
	*s = coada[0];
	for (int i = 0; i < n-1; i++)
		coada[i] = coada[i + 1];
	return --n;
}

int **dezaloca(int **a, int n)
{
	for (int i = 0; i < n; i++)
		delete a[i];
	delete a;
	return a;
}

void bfs(FILE *g, int **a, int n, int s)
{
	int *coada, *m, *p, k(0);
	p = new int[n];
	for (int i = 0; i < n; p[i++] = -1);
	coada = new int[n];
	m = new int[n];
	int nr;
	for (int i = 0; i < n; m[i++] = 0);
	coada[0] = s-1;
	s = s - 1;
	m[s] = 1;
	p[s] = 0;
	nr = 1;
	int gata(0);
	while (nr)
	{
		gata = 0;
		nr = excl_coada(coada, nr, &s, &k);
		for(int i=0; i<n; i++)
			if (a[s][i] == 1 && m[i] == 0)
			{
				if (!gata)
				{
					k++;
					gata = 1;
				}
				nr = ins_coada(coada, nr, i, p, &k);
				m[i] = 1;

			}
	}
	for (int i = 0; i < n; i++)
		fprintf_s(g, "%d ", p[i]);
	delete p;
	delete m;
	delete coada;

}

int main()
{
	int m, n, s, **a, x, y;
	FILE *f, *g;
	fopen_s(&f, "bfs.in", "r");
	fopen_s(&g, "bfs.out", "w");
	fscanf_s(f, "%d %d %d", &n, &m, &s);

	a = aloca(n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			a[i][j] = 0;
	for (int i = 0; i < m; i++)
	{
		fscanf_s(f, "%d %d", &x, &y);
		a[x - 1][y - 1] = 1;
	}

	bfs(g, a, n, s);
	a = dezaloca(a, n);


	return 0;


}