#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	int n, m , s;
	fin >> n >> m >> s;
	vector<int> adjl[n+1];
	vector<int>::iterator it;
	int u, v;
	for (; m > 0; --m) {
		fin >> u >> v;
		adjl[u].push_back(v);
	}

	vector<int> dist(n+1,-1);
	dist[s] = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		u = q.front();
		q.pop();
		for (it = adjl[u].begin(); it != adjl[u].end(); ++it) {
			if (dist[*it] == -1) {
				dist[*it] = dist[u]+1;
				q.push(*it);
			}
		}
	}
	for (int i = 1; i <= n; ++i)
		fout << dist[i] << ' ';
	return 0;
}