#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int n, m, s, a, b, distances[100005], curr, i, size;
bool visited[100005] = { false };
vector<vector<int>> graph;
queue<int> list;

int main()
{
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &s);
	memset(distances, -1, (n + 1) * 4);
	graph = vector<vector<int>>(n + 1);
	for (; m > 0; --m)   scanf("%d%d", &a, &b), graph.at(a).push_back(b);
	list.push(s);
	distances[s] = 0;
	visited[s] = true;
	while (!list.empty())
	{
		curr = list.front();
		list.pop();
		size = graph[curr].size();
		for (i = 0; i < size; ++i)
		{
			int &adNodeDist = distances[graph[curr][i]];
			int &currNodeDist = distances[curr];
			if (currNodeDist != -1)
			{
				if (adNodeDist == -1 || adNodeDist>currNodeDist + 1) adNodeDist = currNodeDist + 1;
				if (!visited[graph[curr][i]])   list.push(graph[curr][i]);
			}
		}
		visited[curr] = true;
	}

	for (i = 1; i <= n; ++i) printf("%d ", distances[i]);
}