#include <fstream>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

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(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++)
		fout << p[i] << " ";
	delete p;
	delete m;
	delete coada;

}

int main()
{
	int m, n, s, **a, x, y;
	fin >> 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++)
	{
		fin >> x >> y;
		a[x - 1][y - 1] = 1;
	}

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


	return 0;


}