#include "stdafx.h"
#include <fstream>
using namespace std;
int a[1000][1000], viz[1000];
int main()
{
	fstream f("bfs.in", ios::in);
	fstream g("bfs.out",ios::out);
	int i, m, n, st, dr, nod, x, y, s, coad[1000], dist[1000];
	f >> n >> m >> s;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y;
		a[x][y] = 1;
	}
	for (i = 1; i<= n; i++)
		dist[i] = -1;
	st = 1;
	dr = 1;
	coad[st] = s;
	viz[s] = 1;
	dist[s] = 0;
	while (st <= dr)
	{
		nod = coad[st];
		for (i = 1; i <= n; i++)
		if (a[nod][i] == 1 && viz[i] == 0)
		{
			dr++;
			coad[dr] = i;
			viz[i] = 1;
			dist[i] = dist[nod] + 1;
		}
		st++;

	}
	for (i = 1; i <= n; i++)
		g << dist[i] << " ";
	return 0;
}