#include <stdio.h>
#include <assert.h>
#include <list>
#include <queue>
#include <iterator>
#include <iostream>

class Graph{
private:
	int size;
	std::list<int> *adj;
public:
	Graph(int size) {
		this->size = size;
		adj = new std::list<int>[size];
	}

	~Graph() {
		delete[] adj;
	}

	void addEdge(int src, int dest) {
		adj[src].push_back(dest);
	}

	std::vector<int> bfs_min_distance(int src) {
		std::vector<bool> visited(size, false);
		std::vector<int> distance(size, -1);
		std::queue<int> Q;

		visited[src] = true;
		distance[src] = 0;
		Q.push(src);

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

			for (std::list<int>::iterator it = adj[index].begin();
				it != adj[index].end(); ++it) {
				if (visited[*it]) {
					continue;
				}

				distance[*it] = distance[index] + 1;
				Q.push(*it);
				visited[*it] = true;
			}
		}

		return distance;
	}
};



int main() {
	int N, M, S, src, dest;
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);

	scanf("%d%d%d", &N, &M, &S);
	assert(2 <= N && N <= 100000);
	assert(1 <= M && M <= 1000000);
	Graph graph(N + 1);

	for (int i = 0 ; i < M ; ++i) {
		scanf("%d%d", &src, &dest);
		graph.addEdge(src, dest);
	}

	std::vector<int> distance = graph.bfs_min_distance(S);

	for (int i = 1 ; i < distance.size() ; ++i) {
		printf("%d ", distance[i]);
	}

	printf("\n");

	//delete [] adj;
	return 0;
}