#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define MaxN 100005
#define MaxM 1000005

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int N, M, S, distances[MaxN];
bool used[MaxN];
vector<int> neighbours[MaxN];
queue<int> q;

int main() {
	memset(distances, -1, MaxN);

	fin >> N >> M >> S;

	for (int i = 0; i < M; ++i) {
		int x, y;
		fin >> x >> y;
		neighbours[x].push_back(y);
	}

	distances[S] = 0;
	used[S] = true;
	q.push(S);
	while (!q.empty()) {
		int v = q.front();
		q.pop();

		for (int i = 0; i < neighbours[v].size(); ++i) {
			int u = neighbours[v][i];
			if (!used[u]) {
				used[u] = true;
				distances[u] = distances[v] + 1;
				q.push(u);
			}
		}
	}

	for (int i = 1; i <= N; ++i) {
		fout << distances[i] << ' ';
	}
	fout << '\n';
	return 0;
}