#include<fstream>
#include<string.h>
using namespace std;
ifstream cin("bfs.in");
ofstream cout("bfs.out");
typedef struct lista
{
	int info;
	lista * next;
}*nod;

nod a[100123];
int d[100123];
void add(int x, nod &p)
{
	nod r = new lista;
	r->info = x;
	r->next = p;
	p = r;
}
nod front;
nod back;
nod q;

void push(int x, nod &q)
{
	nod r = new lista;
	r->info = x;
	r->next = NULL;
	if (!front)
	{
		front = back = r;
		back->next = NULL;
	}
	else
	{
		back->next = r;
		back = r;
		back->next = NULL;
	}
}

bool empty(nod q)
{
	return !q;
}

int pop()
{
	int nr;
	if (!front)
	{
		return 0;
	}
	else
	{
		nod p = front;
		nr = front->info;
		front = front->next;
		delete(p);
		return nr;
	}
}

int n, m, i, j, k;

int main()
{
	memset(d, -1, sizeof(d));
	int start;
	cin >> n >> m >> start;
	while (m--)
	{
		int x, y;
		cin >> x >> y;
		add(y, a[x]);
	}
	push(start, q);
	d[start] = 0;
	while (!empty(front))
	{
		int nr = pop();
		nod r = a[nr];
		while (r)
		{
			if (d[r->info] == -1)
			{
				d[r->info] = d[nr] + 1;
				push(r->info, q);
			}
			r = r->next;
		}
	}
	for (int i = 1; i <= n; ++i) cout << d[i] << " ";
	return 0;
}