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

void bfs_min_distance(std::vector<int> *adj, int src, int &N) {
		std::vector<bool> visited(N + 1, false);
		std::vector<int> distance(N + 1, -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);

	std::vector<int> *adj = new std::vector<int>[N + 1];

	for (int i = 0 ; i < M ; ++i) {
		scanf("%d%d", &src, &dest);
		adj[src].push_back(dest);
	}

	bfs_min_distance(adj, S, N);

	return 0;
}