#include <stdio.h>
#include <stdlib.h>
#define in "bfs.in"
#define out "bfs.out"
#define MAX 100001

struct edge
{
	long node;
	struct edge *next;
};

struct node
{
	int visited;
	long distance;
	struct edge *node;
};

struct node graph[MAX];
long n, s;

struct edge *head;
struct edge *tail;

//add a new edge to graph
void add_edge(long x, long y)
{	
	//create a new node
	struct edge *new_edge;	
	if ((new_edge = (struct edge *)malloc(sizeof(struct edge))) == NULL)
	{
		printf("Not enoug memory\n");
		exit(-1);
	}	
	new_edge->node = y;
	new_edge->next = graph[x].node;
	//add a new tail edge
	graph[x].node = new_edge;
}

void read_file()
{
	FILE *fin;
	long int x, y, m, i;
	
	if ((fin = fopen(in, "r")) == NULL)
	{
		printf("Eroare \n");
		exit(-1);
	}
	//read the two nodes
	fscanf(fin, "%ld%ld%ld", &n, &m, &s);
	for (i = 1; i <=n ; i++)
	{
		graph[i].visited = 0;
		graph[i].node = NULL;
		graph[i].distance = -1;
	}
	for (i = 0; i < m; i++)
	{
		fscanf(fin, "%ld%ld", &x, &y);		
		//add a new node in graph
		add_edge(x, y);
	}
	fclose(fin);
}

//add a new node to queue
void add_queue(long i, long distance)
{
	//create a new node
	struct edge *new_edge;	
	if ((new_edge = (struct edge *)malloc(sizeof(struct edge))) == NULL)
	{
		printf("Not enoug memory\n");
		exit(-1);
	}	
	new_edge->node = i;
	new_edge->next = NULL;	
	graph[i].distance = distance;
	
	if (head == NULL)
	{
		head = new_edge;
		tail = head;
	}
	else
	{
		tail->next = new_edge;
		tail = new_edge;
	}
}

void bfs()
{
	long distance = 0;
	struct edge *temp, *t;
	
	add_queue(s, distance);
	graph[s].visited = 1;
	
	while (head != NULL)
	{
		//refresh the value of distance
		distance = graph[head->node].distance + 1;
	
		//add the unvisited nodes to queue
		for (t = graph[head->node].node; t != NULL; t = t->next)
		{
			if (graph[t->node].visited == 0)
			{
				graph[t->node].visited = 1;
				add_queue(t->node, distance);			
			}
		}
		temp = head;		
		head = head->next;
		free(temp);
	}
	
}

void print_file()
{
	FILE *fout;
	long i;
	fout = fopen(out, "w");
	for (i = 1; i <= n; i++)
		fprintf(fout, "%ld ", graph[i].distance);
	fclose(fout);
}


int main()
{
	read_file();
	
	bfs();
	
	print_file();	

	return 0;
}