#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>

using namespace std;

ifstream cin("bfs.in");
ofstream cout("bfs.out");

int n, m, s;
vector<vector<int>> edges(100001);
vector<int> mini(100001);

int main() {
	cin.sync_with_stdio(false);
	cout.sync_with_stdio(false);

	int v1, v2;
	queue<int> q;

	cin >> n >> m >> s;
	vector<bool> viz(n + 1);

	for (int i = 0; i < m; ++i) {
		cin >> v1 >> v2;
		edges[v1].push_back(v2);
	}

	fill(mini.begin(), mini.begin() + n + 1, -1);

	mini[s] = 0;
	q.push(s);

	while (!q.empty()) {
		int currentNode = q.front(); q.pop();
		viz[currentNode] = true;

		for (auto node : edges[currentNode]) {
			if (!viz[node]) {
				q.push(node);

				if (mini[currentNode] + 1 < mini[node] || mini[node] == -1) {
					mini[node] = mini[currentNode] + 1;
				}
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		cout << mini[i] << ' ';
	}

	return 0;
}