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

int main()
{
	ifstream fi("bfs.in");
	ofstream fo("bfs.out");

	int m, n, s;
	
	fi >> n >> m >> s;
	s--;
	vector<list<int>> graph(n);
	
	for (int i = 0; i < m; i++) {
		int a, b;
		fi >> a >> b;
		a--;
		b--;
		graph[a].push_back(b);
	}

	vector<int> distances(n, -1);
	vector<bool> visited(n, false);
	queue<int> q;
	q.push(s);
	visited[s] = true;
	distances[s] = 0;

	while (q.size() > 0) {
		int node = q.front();
		q.pop();

		for (int i : graph[node]) {
			if (!visited[i]) {
				q.push(i);
				visited[i] = true;
				distances[i] = distances[node] + 1;
			}
		}
	}

	for (int i : distances) {
		fo << i << " ";
	}

	fi.close();
	fo.close();
	return 0;
}