#include <iostream>
#include <vector>
#include <queue>
#include <list>

struct Queue
{
	Queue() = default;

	void enqueue(int k)
	{
		if(elements.size() == capacity)
		{
			throw std::logic_error("overflow");
		}
		elements.push_back(k);
	}

	size_t capacity;
	std::vector<int> elements;
};


void BFS(const std::vector<std::vector<int>>& adj, std::vector<int>& distances, int source)
{
	std::queue<int> q;
	q.push(source);

	while(!q.empty())
	{
		auto u = q.front();
		q.pop();

		for(auto v : adj[u - 1])
		{
			if(distances[v - 1] == -1)
			{
				q.push(v);
				distances[v - 1] = distances[u - 1] + 1;
			}
		}
	}

}

void main()
{
	int N, M, S;
	std::cin >> N >> M >> S;

	std::vector<std::vector<int>> adj(N);
	std::vector<int> distances(N, -1);
	distances[S - 1] = 0;

	int u, v;
	for(int i = 0; i < M; i++)
	{
		std::cin >> u >> v;
		adj[u - 1].push_back(v);
	}

	BFS(adj, distances, S);

	for(auto d : distances)
	{
		std::cout << d << " ";
	}
	std::cout << "\n";


	system("pause");
}