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

#define inf INT_MAX
int const Nlim = 1000005;

int N, M, S;
int x, y;

std::vector<int> Muchii[Nlim];
std::queue<int> Coada;

int distance[Nlim];

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


void citire() {

	f >> N >> M >> S;
	for (int i = 1; i <= M; i++) {
		f >> x >> y;
		Muchii[x].push_back(y);
	}
    
	for (int i = 1; i <= N; i++) {
		distance[i] = -1;
	}

	distance[S] = 0;
}


void BFS() {

	Coada.push(S);

	while (!Coada.empty()) {

		int u = Coada.front();
		Coada.pop();

		for (unsigned int v = 0; v < Muchii[u].size(); v++) {
			int vecin = Muchii[u][v];
			if (distance[vecin]==-1)
			{
				distance[vecin] = distance[u] + 1;
				Coada.push(vecin);
			}
		}
	}

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


int main() {
	citire();
	BFS();

	return 0;

}