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

std::vector<int> BFS(std::vector<std::vector<int>> adj,int node) {
	std::vector<int> distance(adj.size(), -1);
	std::queue<int> Q;

	Q.push(node);

	distance[node] = 0;

	while (!Q.empty()) {
		int x = Q.front();
		Q.pop();

		for (auto neighbour : adj[x]) {

			if (distance[neighbour]==-1) {
				distance[neighbour] = distance[x] + 1;
				Q.push(neighbour);
			}
		}
	}

	return distance;
}

int main(void)
{
	std::ifstream in("bfs.in");
	int n, m,node;
	in >> n >> m >> node;

	std::vector<std::vector<int>> adj(n);

	for (int i = 0; i < m; i++) {
		int x, y;
		in >> x >> y;
		adj[--x].push_back(--y);
	}

	in.close();

	std::ofstream out("bfs.out");

	for (auto x : BFS(adj, --node)) {
		out << x << " ";
	}

	return 0;
}