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

void BFS(vector<vector<int>>& arches, vector<int>& visited, int S, int N) {
	queue<int> nodes;
	nodes.push(S);
	++visited[S - 1];
	while (!nodes.empty()) {
		int node = nodes.front();
		nodes.pop();
		int length = arches[node - 1].size();
		for (int i = 1; i < length; ++i) {
			if (visited[arches[node - 1][i] - 1] == -1) {
					visited[arches[node - 1][i] - 1] = visited[node - 1] + 1;
					nodes.push(arches[node - 1][i]);
			}
		}
	}
}

int main() {
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	int N, M, S;
	fin >> N >> M >> S;
	vector<vector<int>> arches(N, vector<int>(1, 0));
	vector<int> visited(N, -1);
	int x, y;
	for (int i = 0; i < M; ++i) {
		fin >> x >> y;
		arches[x - 1].push_back(y);
	}
	BFS(arches, visited, S, N);
	for (int i = 0; i < N; ++i)
		fout << visited[i] << " ";
	return 0;
}