#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct mystruct
{
	int node;
	int level;
	
}bfsnode;

typedef struct mystruct1
{
	int number_of_neighbors;
	int *neighbors;

}AdjacencyList;

int main(int argc, char const *argv[])
{
	FILE *read = fopen("bfs.in", "r");
	FILE *write = fopen("bfs.out", "w");


	int number_of_vertices, number_of_arcs;
	int vertex;

	fscanf(read, "%d%d%d", &number_of_vertices, &number_of_arcs, &vertex);
	AdjacencyList *adjlist = calloc(number_of_vertices+1, sizeof(AdjacencyList));

	int x,y;

	for (int i = 0; i < number_of_arcs; i++)
	{
		fscanf(read, "%d%d", &x, &y);

		if (adjlist[x].number_of_neighbors == 0)
		{
			adjlist[x].number_of_neighbors = 1;

			adjlist[x].neighbors = calloc(1, sizeof(int));
			adjlist[x].neighbors[0] = y;

		}
		else
		{
			adjlist[x].number_of_neighbors ++;

			adjlist[x].neighbors = realloc(adjlist[x].neighbors, adjlist[x].number_of_neighbors * sizeof(int));
			adjlist[x].neighbors[adjlist[x].number_of_neighbors - 1]=y;

		}

	}

	int nodes_in_bfs=1;

	bfsnode *array = calloc(1, sizeof(bfsnode));
	int *levels = calloc(number_of_vertices + 1, sizeof(int));
	bool * visited = calloc(number_of_vertices + 1, sizeof(bool));

	for(int i = 1; i <= number_of_vertices; i++)
		levels[i] = -1;

	levels[vertex] = 0;

	visited[vertex] = true;
	array[0].node = vertex;
	array[0].level = 0;

	int i = 0;

	while (i < nodes_in_bfs)
	{

		for(int j = 0; j < adjlist[array[i].node].number_of_neighbors; j++)
			if (visited[adjlist[array[i].node].neighbors[j]] == false)
			{
				visited[adjlist[array[i].node].neighbors[j]] = true;	
				nodes_in_bfs ++;
				array = realloc(array, nodes_in_bfs * sizeof(bfsnode));
				array[nodes_in_bfs - 1].node = adjlist[array[i].node].neighbors[j];
				array[nodes_in_bfs - 1].level = array[i].level + 1;

				if ( levels[adjlist[array[i].node].neighbors[j]] == -1 || levels[adjlist[array[i].node].neighbors[j]] > array[nodes_in_bfs - 1].level )
					levels[adjlist[array[i].node].neighbors[j]]	= array[nodes_in_bfs - 1].level;			

			}

		i++;

	}

	for (int i = 1; i <= number_of_vertices; i++)
		if (i == number_of_vertices)
			fprintf(write, "%d\n", levels[i]);
		else
			fprintf(write, "%d ", levels[i]);

	for (int i = 1; i <= number_of_vertices; i++)
		if (adjlist[i].number_of_neighbors > 0)
			free(adjlist[i].neighbors);
	free(adjlist);

	fclose(read);
	fclose(write);
	
	return 0;
}