#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	int n, m, s;
	ifstream fin("bfs.in");

	fin >> n >> m >> s;
	vector<int> costsFromS(n, -1);
	vector<vector<int>> lista(n);

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

	queue<int> q;
	costsFromS[s - 1] = 0;
	q.push(s - 1);

	while (!q.empty()) {
		int t = q.front();
		q.pop();
		for (int i = 0; i < lista[t].size(); ++i) {
			if (costsFromS[lista[t][i]] == -1) {
				costsFromS[lista[t][i]] = costsFromS[t] + 1;
				q.push(lista[t][i]);
			}
		}
	}

	ofstream fout("bfs.out");
	for (int i = 0; i < n; ++i) {
		fout << costsFromS[i] << ' ';
	}
	fout.close();

	return 0;
}