#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int main()
{

	FILE * f = fopen("bfs.in", "r");
	int n, m, s;
	fscanf(f, "%i%i%i", &n, &m, &s);
	vector<vector<int> > a(n);
	vector<int> viz(n);

	int i, q, w;

	for (i = 0; i < n; i++)
	{
		viz[i] = 0;
	}
	viz[s-1] = 1;
	for (i = 0; i < m; i++)
	{
		fscanf(f, "%i%i", &q, &w);
		a[q-1].push_back(w-1);
	}

	fclose(f);
	queue<int> coada;
	coada.push(s-1);

	while(!coada.empty())
	{
		int e = coada.front();
		coada.pop();

		int len = a[e].size();
		for (i = 0; i < len; i++)
		{
			if (viz[a[e][i]] == 0)
			{
				coada.push(a[e][i]);
				viz[a[e][i]] = viz[e] + 1;
			}
		}
	}

	f = fopen("bfs.out", "w");
	for (i = 0; i < n; i++)
		if (viz[i] == 0)
			fprintf(f, "%i ", -1);
		else
			fprintf(f, "%i ", viz[i] - 1);
	fclose(f);
	return 0;

}