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

using namespace std;

long N, M, S;
bool color[100000];
long parent[100000];
long dist[100000];

void bfs (const std::vector< std::vector<long> > &adjList) {
	std::queue<long> Q;

	Q.push(S);
	dist[S] = 0;

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

		color[u] = 1; //gray
		for (long i = 0; i < adjList[u].size(); i++) {
			if (color[adjList[u][i]] == 0 && u != adjList[u][i]) {
				dist[adjList[u][i]] = dist[u] + 1;
				parent[adjList[u][i]] = u;
				Q.push(adjList[u][i]);
			}
		}
		color[u] = 2; //black
	}
}

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

	bfs(adjList);

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

	fclose(input);
	fclose(output);

	return 0;
}