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

typedef struct graphVertex {
	int numNeighbours;
	int* neighbours;
	int name;
	int weights;
} graphVertex;
int NumberOfNodes, NumberOfEdges, root;
graphVertex* readGraphVertex(const char* fileName)
{
	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return NULL;

	fscanf(f, "%i%i%i", &NumberOfNodes, &NumberOfEdges, &root);
	graphVertex* nodes = (graphVertex*)malloc((NumberOfNodes + 1) * sizeof(graphVertex));
	if (nodes == NULL)
		return nodes;
	for (int i = 1; i <= NumberOfNodes; i++) {
		nodes[i].name = i;
		nodes[i].numNeighbours = 0;
		nodes[i].neighbours = NULL;
		nodes[i].weights = -1;
	}
	int stanga, dreapta;
	for (int i = 0; i < NumberOfEdges; i++) {
		fscanf(f, "\n%i%i", &stanga, &dreapta);
		nodes[stanga].numNeighbours++;
		nodes[stanga].neighbours = (int*)realloc(nodes[stanga].neighbours, (nodes[stanga].numNeighbours) * sizeof(int));
		nodes[stanga].neighbours[nodes[stanga].numNeighbours - 1] = dreapta;
	}
	fclose(f);
	return nodes;
}
int queue[100001];
void bfs(graphVertex* graph, int startnode)
{
	graph[startnode].weights = 0;
	int nivel = 1;
	queue[nivel] = startnode;
	int limit = 1;
	while (limit <= nivel) {
		int value = queue[limit];
		limit++;
		for (int i = 0; i < graph[value].numNeighbours; i++)
			if (graph[graph[value].neighbours[i]].weights == -1) {
				nivel++;
				queue[nivel] = graph[graph[value].neighbours[i]].name;
				graph[graph[value].neighbours[i]].weights = 1 + graph[value].weights;
			}
	}
}
int main()
{
	graphVertex* graph = readGraphVertex("bfs.in");
	bfs(graph, root);
	FILE* f = fopen("bfs.out", "w");
	for (int i = 1; i <= NumberOfNodes; i++)
		fprintf(f, "%i ", graph[i].weights);
	fclose(f);
}