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

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

	~Graph() {
		delete[] adj;
	}

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

	void 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 (int i = 0 ; i < adj[index].size() ; ++i) {
				if (visited[adj[index][i]]) {
					continue;
				}

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

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



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);
	}

	graph.bfs_min_distance(S);

	return 0;
}