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

void BFS(map<int, vector<int>>& archesMap, vector<int>& visited, map<int, vector<int>>::iterator itr, int& S, int& N) {
	queue<int> nodes;
	nodes.push(S);
	++visited[S - 1];
	while (!nodes.empty()) {
		int node = nodes.front();
		nodes.pop();
		itr = archesMap.find(node);
		if (itr != archesMap.end()) {
			int length = itr->second.size();
			for (int i = 0; i < length; ++i) {
				if (visited[itr->second[i] - 1] == -1) {
					visited[itr->second[i] - 1] = visited[node - 1] + 1;
					nodes.push(itr->second[i]);
				}
			}
		}
	}
}

int main() {
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	int N, M, S;
	fin >> N >> M >> S;
	vector<int> visited(N, -1);
	map<int, vector<int>> archesMap;
	map<int, vector<int>>::iterator itr;
	int x, y;
	for (int i = 0; i < M; ++i) {
		fin >> x >> y;
		itr = archesMap.find(x);
		if (itr != archesMap.end())
			itr->second.push_back(y);
		else {
			vector<int> vect;
			vect.push_back(y);
			archesMap.insert(pair<int, vector<int>>(x, vect));
		}
	}
	BFS(archesMap, visited, itr, S, N);
	for (int i = 0; i < N; ++i)
		fout << visited[i] << " ";
	return 0;
}