#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define type int

typedef struct listNode
{
	type element;
	listNode* next;
	listNode* prev;
};

void pushCoada(listNode*& first, listNode*& last, type element)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->element = element;
	node->next = NULL;
	node->prev = last;
	if (last == NULL)
	{
		last = node;
		first = node;
		return;
	}

	last->next = node;
	last = last->next;
}
void popCoada(listNode*& first, listNode*& last)
{
	if (first == NULL)
		return;
	if (first->next == NULL)
	{
		free(first);
		first = NULL;
		last = NULL;
		return;
	}
	listNode* aux = first;
	first = first->next;
	first->prev = NULL;
	free(aux);
}
listNode* graph[100001];
void insertNodeInGraph(int graphNo, type element)
{
	listNode* p = graph[graphNo];
	if (p == NULL)
		pushCoada(graph[graphNo], p, element);
	else
	{
		while (p->next != NULL)
			p = p->next;
		pushCoada(graph[graphNo], p, element);
	}
}

int n, m, q, visited[100001];
void readGraph(char* filename)
{
	FILE* fin = fopen(filename, "r");

	fscanf(fin, "%d%d%d", &n, &m, &q);
	int x, y;

	for (int i = 1; i <= n; i++)
	{
		graph[i] = NULL;
	}
	for (int i = 1; i <= m; i++)
	{
		fscanf(fin, "%d%d", &x, &y);
		insertNodeInGraph(x, y);
	}
}

int v[100001];
void BFS_recursiv(listNode* first, listNode* last, int i)
{
	while (graph[i] != NULL)
	{
		if (!visited[graph[i]->element])
		{
			pushCoada(first, last, graph[i]->element);
			v[graph[i]->element] = v[i] + 1;
			visited[graph[i]->element] = 1;
			if (i == q && i == graph[i]->element)
				v[i] = 0;
		}
		graph[i] = graph[i]->next;
	}
	if (first == NULL)
		return;
	int el = first->element;
	popCoada(first, last);
	BFS_recursiv(first, last, el);
}
int main()
{
	readGraph((char*)"bfs.in");
	//PrintGraph();
	listNode* first = NULL, * last = NULL;
	for (int i = 1; i <= n; i++)
	{
		v[i] = -1;
	}
	v[q] = 0;
	BFS_recursiv(first, last, q);
	FILE* fout = fopen("bfs.out", "w");
	for (int i = 1; i <= n; i++)
	{
		fprintf(fout,"%d ", v[i]);
	}
}