#include <fstream>
#include<queue>
using namespace std;

queue <int> q;
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)
{
	coada[n] = s;
	return ++n;
}*/

/*int excl_coada(int *coada, int n, int *s)
{
	*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 *m, *p;
	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);
	s = s - 1;
	q.push(s);
	m[s] = 1;
	p[s] = 0;
	int cost = 0;
	while (!q.empty())
	{
		s = q.front();
		q.pop();
		//nr = excl_coada(coada, nr, &s);
		cost = p[s];
		for(int i=0; i<n; i++)
			if (a[s][i] == 1 && m[i] == 0)
			{
				q.push(i);
				//nr = ins_coada(coada, nr, i);
				p[i] = cost + 1;
				m[i] = 1;
			}
	}
	for (int i = 0; i < n; i++)
		fout << p[i] << " ";
	delete p;
	delete m;
	//delete coada;

}

int main()
{
	int m, n, t, **a;
	fin >> n >> m >> t;

	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++)
	{
		int x, y;
		fin >> x >> y;
		a[x - 1][y - 1] = 1;
	}

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

	return 0;
}