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

queue <int> q;
ifstream fin("bfs.in");
ofstream fout("bfs.out");


void bfs(int **a, int n, int s)
{
	int *m, *p;
	p = new int[n];
	for (int i = 0; i < n; p[i++] = NULL);
	m = new int[n];
	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();
		cost = p[s];
		for(int i=0; i<n; i++)
			if (a[s][i] == 1 && m[i] == 0)
			{
				q.push(i);
				p[i] = cost + 1;
				m[i] = 1;
			}
	}
	for (int i = 0; i < n; i++)
	{
		if (p[i] >= 0)
			fout << p[i] << " ";
		else
			fout << "-1 ";
	}
	delete p;
	delete m;
	//delete coada;

}

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

	int **a;
	a = new int*[n];
	for (int i = 0; i < n; i++)
		a[i] = new int[n];
	for (int i = 0; i < m; i++)
	{
		int x, y;
		fin >> x >> y;
		a[x - 1][y - 1] = 1;
	}

	bfs(a, n, t);

	for (int i = 0; i < n; i++)
		delete a[i];
	delete a;

	return 0;
}