#include <fstream>
using namespace std;
struct nodul { int val;
nodul*urm;
};
nodul*a[100000];
void add(nodul*&d, int valoare)
{
	nodul*p = new nodul;
	p->val = valoare;
	p->urm = d;
	d = p;

}
int viz[100000];
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[100000], dist[100000];
	f >> n >> m >> s;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y;
		add(a[x], y);
	}
	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 (nodul*q = a[nod]; q!= NULL; q = q->urm)
		if (viz[q->val] == 0)
		{
			dr++;
			coad[dr] = q->val;
			viz[q->val] = 1;
			dist[q->val] = dist[nod] + 1;
		}
		st++;

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