#include <iostream>
#include <fstream>

using namespace std;

int v[10001][10001], rez[10001], n, m, s;

void bfs(int nodStart)
{
	int coada[10001], nr, poz, nod, i;

	coada[1] = nodStart;
	nr = 1;
	poz = 1;

	while(poz <= nr)
	{
		nod = coada[poz];

		for(i=1; i<=n; i++)
		{
			if(v[nod][i] == 1 && rez[i] == -1)
			{
				nr++;
				coada[nr] = i;
				rez[i] = rez[nod] + 1;
			}
		}

		poz++;
	}
}

int main()
{
	ifstream f("bfs.in");
	ofstream g("bfs.out");
	int i, x, y;

	f >> n >> m >> s;

	for(i=1; i<=m; i++)
	{
		f >> x >> y;

		v[x][y] = 1;
	}

	for(i=1; i<=n; i++)
	{
		rez[i] = -1;
	}

	rez[s] = 0;

	bfs(s);

	for(i=1; i<=n; i++)
		g << rez[i] << ' ';

	f.close();
	g.close();
	return 0;
}