#include <cstdio>

const unsigned int MAX_VERTICES(100001);

struct list_element
{
	unsigned int vertex;
	struct list_element *next;
} *graph [MAX_VERTICES];

unsigned int path_cost [MAX_VERTICES];
unsigned int queue [MAX_VERTICES];

void BreadthFirstSearch (unsigned int s, unsigned int n)
{
	unsigned int *push(queue), *pop(queue), neighbor, cost;
	struct list_element *iterator;
	*push = s;
	++push;
	do
	{
		neighbor = *pop;
		++pop;
		cost = path_cost[neighbor] + 1;
		for (iterator = graph[neighbor] ; iterator ; iterator = iterator->next)
			if (!path_cost[iterator->vertex] && iterator->vertex != s)
			{
				*push = iterator->vertex;
				++push;
				path_cost[iterator->vertex] = cost;
			}
	}
	while (pop < push);
}

int main (void)
{
	std::freopen("bfs.in","r",stdin);
	std::freopen("bfs.out","w",stdout);
	unsigned int n, m, s;
	std::scanf("%u%u%u",&n,&m,&s);
	++n;
	unsigned int from, to, *from_ptr(&from), *to_ptr(&to);
	struct list_element *new_edge;
	do
	{
		std::scanf("%u%u",from_ptr,to_ptr);
		new_edge = new struct list_element;
		new_edge->vertex = to;
		new_edge->next = graph[from];
		graph[from] = new_edge;
		--m;
	}
	while (m);
	std::fclose(stdin);
	BreadthFirstSearch(s,n);
	unsigned int *iterator(path_cost + 1), *end(path_cost + n);
	while (true)
	{
		if (*iterator)
			std::printf("%u",*iterator);
		else if (iterator - path_cost != s)
			std::printf("-1");
		else
			std::printf("0");
		++iterator;
		if (iterator == end)
			break;
		std::printf(" ");
	}
	std::printf("\n");
	std::fclose(stdout);
	return 0;
}