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

int n, m, s, a, b, distances[100005], curr, i, adListSize, heap[100005], heapInsert = 0,heapCurr;
bool visited[100005] = { false };
vector<vector<int>> graph;

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

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