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



#define type int
int visited[100001];

typedef struct listNode;

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



int muchii[1000001][2];

int citireFisier(char* filename,int &node,int &noduri)
{
	FILE* fin = fopen(filename, "r");
	if (fin == NULL)
	{
		exit(0);
	}

	int nrmuchii;
	fscanf(fin, "%d%d%d", &noduri, &nrmuchii,&node);
	int n, m;
	for (int i = 1; i <= nrmuchii; i++)
	{
		fscanf(fin, "%d%d", &n, &m);
		muchii[i][1] = n;
		muchii[i][2] = m;
	}
	return nrmuchii;
}

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);
}


int cost[100001];
void BFS(listNode* first, listNode* last,int noduri, int node)
{
	pushCoada(first, last, node);
	int ok = 0;
	while (first != NULL)
	{
		for (int i = 1; i <= noduri; i++)
		{
			if (visited[muchii[i][2]] == 0 && muchii[i][1] == first->element)
			{
				if (muchii[i][1] != muchii[i][2])
				{
					visited[muchii[i][2]] = visited[first->element] + 1;
					pushCoada(first, last, muchii[i][2]);
				}
				else
					ok = 1;
			}
		}
		popCoada(first, last);
	}
	if (ok)
		visited[node] = -1;
}

int main()
{
	int node = 0,noduri;
	int nrmuchii = citireFisier((char*)"bfs.in",node,noduri);

	listNode* head = NULL;
	listNode* first = NULL, * last = NULL;
	BFS(first, last, nrmuchii, node);




	FILE* fout = fopen("bfs.out", "w");
	for (int i = 1; i <= noduri; i++)
	{
		if (visited[i] > 0)
			fprintf(fout,"%d ", visited[i]);
		else if (visited[i] == 0)
			fprintf(fout,"-1 ");
		else if (visited[i] == -1)
			fprintf(fout,"0 ");
	}
}