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

typedef struct list_node
{
	unsigned long int node;
	list_node* next;
}list_node;
#define VERIF if(nou==NULL) {printf("eroare la alocare");return;}
void insert_node(list_node** start, list_node** end, unsigned long int val)
{
	list_node* nou = (list_node*)malloc(sizeof(list_node));
	VERIF
		nou->node = val;
	nou->next = NULL;
	if (*start == NULL)
	{
		(*start) = (*end) = nou;
		return;
	}
	(*end)->next = nou;
	(*end) = nou;
}
void remove_head_of_list(list_node** start)
{
	if (*start == NULL)
		return;
	list_node* the_one = *start;
	(*start) = (*start)->next;
	free(the_one);
}


//push
void push_queue(list_node** start, list_node** end, unsigned long int val)
{
	insert_node(start, end, val);
}
//pop
unsigned long int pop_queue(list_node** start)
{
	unsigned long int aux = (*start)->node;
	remove_head_of_list(start);
	return aux;
}

typedef struct node {
	unsigned long int val;
	unsigned long int nr_neib;
	node** neib;
}node;
typedef struct graph_str
{
	unsigned long int n;
	unsigned long int m;
	node* nodes;
}graph_str;
graph_str read_graph(FILE* f, graph_str graph,int *visited)
{
	for (unsigned long int i = 0; i < graph.n; i++)
	{
		graph.nodes[i].val = i + 1;
		graph.nodes[i].nr_neib = 0;
		graph.nodes[i].neib = NULL;
		visited[i] = -1;
	}
	unsigned long int x, y;
	while (!feof(f))
	{
		fscanf(f, "%ld %ld", &x, &y);
		if (x != y)
		{
			graph.nodes[x - 1].nr_neib++;
			graph.nodes[x - 1].neib = (node**)realloc(graph.nodes[x - 1].neib, sizeof(node*) * graph.nodes[x - 1].nr_neib);
			graph.nodes[x - 1].neib[graph.nodes[x - 1].nr_neib - 1] = &graph.nodes[y - 1];
		}
	}
	return graph;
}
void BFS(graph_str graph, unsigned long start_num, int* visited)
{
	list_node* start, * end;
	start = end = NULL;
	push_queue(&start, &end, start_num);
	visited[start_num - 1] = 0;
	unsigned long int current_num;
	while (start)
	{
		current_num = pop_queue(&start);
		printf("%ld ", current_num);
		for (unsigned long int i = 0; i < graph.nodes[current_num - 1].nr_neib; i++)
		{
			if (visited[graph.nodes[current_num - 1].neib[i]->val-1]==-1)
			{
				visited[graph.nodes[current_num - 1].neib[i]->val-1] = visited[current_num-1]+1;
				push_queue(&start, &end, graph.nodes[current_num - 1].neib[i]->val);
			}
		}
	}
}
void print_result(int* visited, graph_str graph)
{
	FILE* f = fopen("bfs.out", "w");
	if (f == NULL)
	{
		return;
	}
	for (unsigned long int i = 0; i < graph.n; i++)
	{
		fprintf(f, "%d ", visited[i]);
	}
	fclose(f);
}
int main()
{
	unsigned long int s;
	FILE* f = fopen("bfs.in", "r");
	if (f == NULL)
	{
		return 0;
	}
	graph_str graph;
	fscanf(f, "%ld %ld %ld", &graph.n, &graph.m, &s);
	int* visited = (int*)malloc(sizeof(int) * graph.n);
	graph.nodes = (node*)malloc(sizeof(node) * graph.n);
	graph = read_graph(f, graph,visited);
	fclose(f);
	BFS(graph, s, visited);
	print_result(visited, graph);

	return 0;
}