#include <fstream>
#include <vector>
#include <list>
#include <queue>

typedef std::list<unsigned int> edge;
typedef std::vector<edge> graph;

void BreadthFirstSearch (graph &g, unsigned int source, std::vector<signed int> &path_cost)
{
	std::queue<unsigned int> queue;
	queue.push(source);
	std::vector<bool> visited(g.size(),false);
	visited[source] = true;
	unsigned int neighbor, cost, node;
	edge::const_iterator iterator, end;
	do
	{
		neighbor = queue.front();
		cost = path_cost[neighbor] + 1;
		queue.pop();
		for (iterator = g[neighbor].begin(), end = g[neighbor].end() ; iterator != end ; ++iterator)
			if (!visited[node = *iterator])
			{
				visited[node] = true;
				path_cost[node] = cost;
				queue.push(node);				
			}
	}
	while (!queue.empty());
}

int main (void)
{
	unsigned int n, m, s;
	std::ifstream input("bfs.in");
	input >> n >> m >> s;
	++n;
	graph g(n);
	std::vector<signed int> path_cost(n,-1);
	path_cost[s] = 0;
	unsigned int from, to;
	do
	{
		input >> from >> to;
		g[from].push_front(to);
		--m;
	}
	while (m);
	input.close();
	BreadthFirstSearch(g,s,path_cost);
	std::ofstream output("bfs.out");
	std::vector<signed int>::const_iterator iterator(&path_cost[1]), end(path_cost.end());
	signed int value;
	while (true)
	{
		value = *iterator;
		if (value == -1)
			output << "-1";
		else
			output << value;
		++iterator;
		if (iterator == end)
			break;
		output.put(' ');
	}
	output.put('\n');
	output.close();
	return 0;
}