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

int main() {
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	int nr, arches, s;
	scanf("%d %d %d", &nr, &arches, &s);
	vector<stack<int>> nodes(nr + 1, stack<int>());
	vector<int> length(nr + 1, -1);
	for (; arches; arches--) {
		int from, to;
		scanf("%d %d", &from, &to);
		nodes[from].push(to);
	}
	length[s] = 0;
	queue<int> list;
	for (list.push(s); list.size(); list.pop()) {
		for (int from = list.front(); nodes[from].size(); nodes[from].pop()) {
			int to = nodes[from].top();
			if (length[to] < 0) {
				length[to] = length[from] + 1;
				list.push(to);
			}
		}
	}
	for (int i = 1; i <= nr; i++) {
		cout << length[i] << ' ';
	}
	return 0;
}