#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

std::vector<std::vector<int> >la;
std::vector<int> distanta;
int N, M, start;

void citire() {
	std::ifstream f("bfs.in");
	f >> N >> M >> start;
	la.resize(N + 1);
	distanta.resize(N + 1);
	
	for (int i = 0; i <= M; ++i) {
		int x, y;
		f >> x >> y;
		la[x].push_back(y);
	}
}

void bfs() {
	std::queue<int> coada;
	coada.push(start);
	
	std::fill(distanta.begin(), distanta.end(), -1); // daca distanta[i] == -1 atunci e nevizitat
	distanta[start] = 0;

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

		for(int vecin : la[nod])
			if (distanta[vecin] == -1) {
				distanta[vecin] = 1 + distanta[nod];
				coada.push(vecin);
			}
	}
}

void afis() {
	std::ofstream g("bfs.out");
	for (int i = 1; i <= N; ++i)
		g << distanta[i] << ' ';
}

int main()
{
	citire();
	bfs();
	afis();
}