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

constexpr auto INF = 100001;

using namespace std;

int main() {
	vector<vector<int>> graph;
	ifstream f("bfs.in");
	int n, m, s;
	f >> n >> m >> s;
	graph.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		f >> a >> b;
		graph[a].push_back(b);
	}

	f.close();

	vector<bool> vis(n + 1);
	vector<int> dist(n + 1);
	for (int i = 0; i <= n; i++)
		vis[i] = false, dist[i] = -1;
	queue<int> list;
	list.push(s);
	dist[s] = 0;
	vis[s] = true;
	while (!list.empty())
	{
		int i = list.front();
		for (auto it : graph[i])
		{
			if (vis[it] == false)
			{
				vis[it] = true;
				dist[it] = dist[i] + 1;
				list.push(it);
			}
		}
		list.pop();
	}

	ofstream g("bfs.out");
	for (int i = 1; i <= n; i++)
		g << dist[i] << " ";
	g.close();
}