#include<iostream>
//#include<cstdlib>
#include<fstream>
#define leng 100001
using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

struct nod {
	int info;
	int visited;
	nod* next;
};

int exists(nod *p, int info) {
	nod *q = p;
	while (q != NULL) {
		if (q->info == info)
			return 1;
		q = q->next;
	}
	return 0;
}

void add_node(nod *&p, nod *&u, int i) {
	if (!exists(p, i)) {
		if (p == NULL) {
			p = new nod;
			p->info = i;
			p->visited = 0;
			u = p;
			u->next = NULL;
		}
		else {
			nod *c = new nod;
			c->info = i;
			c->visited = 0;
			u->next = c;
			u = c;
			u->next = NULL;
		}
	}
}

int main()
{
	int N, M, S;
	f >> N >> M >> S;

	nod* L[leng], *LF[leng];
	//nod **L = new nod*[N+1];
	//nod **LF = new nod*[N+1];
	int i, j;
	nod *p, *u;
	p = u = NULL;
	//int viz[100001];

	for (int i = 0; i < leng; i++) {
		L[i] = LF[i] = NULL;
	}


	while (M--) {
		f >> i >> j;
		//g << i << j;
		add_node(L[i], LF[i], j);
	}
	/*
	for (int i = 0; i < leng; i++) {
		if (L[i] != NULL) {
			cout << i << ": ";
			nod *c = L[i];
			while (c != NULL) {
				cout << c->info << " ";
				c = c->next;
			}
			cout << endl;
		}
	}
	*/
	//for (int i = 1; i <= N; i++)
		//viz[i] = 0;

	add_node(p, u, S);
	nod *current = L[S];

	int * vis = new int[leng];
	int * cost = new int[leng];

	for (int i = 0; i < leng; i++)
		vis[i] = 0;

	for (int i = 0; i < leng; i++)
		cost[i] = -1;
	vis[S] = 1;
	cost[S] = 0;

	while (p != NULL) {
		while (current != NULL) {
			if (vis[current->info] == 0) {
				add_node(p, u, current->info);
				if(cost[current->info] < 0)
				cost[current->info] = cost[p->info] + 1;
				}
				current = current->next;
			}
		if (p->next != NULL) {
			current = L[p->next->info];
		}
		//cout << p->info << " ";
		vis[p->info] = 1;
		p = p->next;
	}
	//cout << endl;

	for (int i = 1; i <= N; i++)
		g << cost[i] << " ";

	f.close();
	g.close();
	//system("Pause");
	return 0;
}