#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>

using namespace std;

long N, M, S;
long dist[100001];

int main () {
	FILE* input = fopen("bfs.in", "r");
	FILE* output = fopen("bfs.out", "w");

	fscanf(input, "%ld %ld %ld", &N, &M, &S);

	for (long i = 1; i <= N; i++) dist[i] = -1;
	std::vector< std::vector<long> > adjList(N + 1, std::vector<long>());

	long u, v;
	for (long i = 0; i < M; i++) {
		fscanf(input, "%ld %ld", &u, &v);

		adjList[u].push_back(v);
	}

	queue<long> Q;
	dist[S] = 0;
	Q.push(S);

	while (!Q.empty()) {
		long u = Q.front();

		Q.pop();

		for (long i = 0; i < adjList[u].size(); i++) {
			if (dist[adjList[u][i]] == -1) {
				Q.push(adjList[u][i]);
				dist[adjList[u][i]] = dist[u] + 1;
			}
		}
	}


	for (long i = 1; i <= N; i++) {
		fprintf(output, "%ld ", dist[i]);
	}

	fclose(input);
	fclose(output);

	return 0;
}