#include <bits/stdc++.h>
using namespace std;

#define INF 1'000'000'000U

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

	uint n, m, s;
	fin >> n >> m >> s;
	--s;

	vector<vector<uint>> adj(n);

	for (uint i = 0, x, y; i < m; ++i) {
		fin >> x >> y;
		adj[x - 1].push_back(y - 1);
	}

	vector<uint> dist(n, INF);
	dist[s] = 0;

	queue<uint> q;
	q.push(s);

	while (!q.empty()) {
		uint current = q.front();
		q.pop();

		for (uint neigh : adj[current])
			if (dist[current] + 1 < dist[neigh]) {
				dist[neigh] = dist[current] + 1;
				q.push(neigh);
			}
	}

	for (uint& x : dist)
		if (x == INF)
			fout << "-1 ";
		else
			fout << x << ' ';
	fout << '\n';
}