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

using namespace std;

ifstream f;
ofstream g;

f.open("bfs.in");
g.open("bfs.out");

int n, m;
vector<vector<int>>graph;
vector<bool>visited;
vector<int>cost;

void bfs(int vertex)
{
	if (vertex < 0 || vertex > n - 1)
		return;
	queue<int>q;
	int elem;
	q.push(vertex);
	visited[vertex] = true;
	cost[vertex] = 0;
	while (!q.empty())
	{
		elem = q.front();
		for (int i = 0; i < graph[elem].size();i++)
			if (!visited[graph[elem][i]])
			{
				q.push(graph[elem][i]);
				cost[graph[element[i]]] = cost[element] + 1;
				visited[graph[elem][i]] = true;
			}
		q.pop();
	}
}

int main()
{
	int x, y, s;
	f >> n >> m >> s;
	for (i = 0; i < m; i++)
	{
		f >> x >> y;
		x--; y--;
		graph[x].push_back(y);
	}
	bfs(s - 1);
	for (i = 0; i < n; i++)
		g << cost[i] << " ";
    return 0;
}