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

typedef struct vertex {
	int name;
	struct vertex* neighbors;
	int numNeighbors;
	int weights;
} vertex;

typedef struct graphVertex {
	int numNodes;
	int numEdges;
	vertex* nodes;
} graphVertex;

typedef struct queue {
	int element;
	struct queue* next;
} queue;

void Qpush(queue** coada, int value)
{
	queue* aux = (queue*)malloc(sizeof(queue));
	aux->element = value;
	aux->next = NULL;

	if ((*coada) == NULL) {
		(*coada) = aux;
		return;
	}
	queue* ptr = (*coada);
	while (ptr->next != NULL) {
		ptr = ptr->next;
	}
	ptr->next = aux;
	aux->next = NULL;
}
int Qpop(queue** coada)
{
	int node = (*coada)->element;
	(*coada) = (*coada)->next;
	return node;
}
int nr_elem(queue* coada)
{
	int count = 0;
	while (coada != NULL) {
		count++;
		coada = coada->next;
	}
	return count;
}

graphVertex readGraphVertex(const char* fileName, int* s)
{
	graphVertex graph;
	graph.numEdges = 0;
	graph.numNodes = 0;
	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;

	fscanf(f, "%i %i %i", &(graph.numNodes), &(graph.numEdges), &(*s));
	graph.nodes = (vertex*)malloc(sizeof(vertex) * (graph.numNodes + 1));
	if (graph.nodes == NULL)
		return graph;
	for (int i = 1; i <= graph.numNodes; i++) {
		graph.nodes[i].name = i;
		graph.nodes[i].numNeighbors = 0;
		graph.nodes[i].neighbors = NULL;
		graph.nodes[i].weights = -1;
	}
	int e1, e2;
	for (int i = 1; i <= graph.numEdges; i++) {
		fscanf(f, "%d %d", &e1, &e2);
		graph.nodes[e1].numNeighbors++;
		graph.nodes[e1].neighbors = (vertex*)realloc(graph.nodes[e1].neighbors, sizeof(vertex) * (graph.nodes[e1].numNeighbors + 1));
		graph.nodes[e1].neighbors[graph.nodes[e1].numNeighbors].name = e2;
	}

	fclose(f);
	return graph;
}
void bfs_search(graphVertex graph, int startNode, const char* filename)
{
	queue* coada = NULL;
	Qpush(&coada, startNode);
	graph.nodes[startNode].weights = 0;
	while (nr_elem(coada) > 0) {
		int node = Qpop(&coada);
		for (int i = 1; i <= graph.nodes[node].numNeighbors; i++) {
			if (graph.nodes[graph.nodes[node].neighbors[i].name].weights == -1) {
				Qpush(&coada, graph.nodes[node].neighbors[i].name);
				graph.nodes[graph.nodes[node].neighbors[i].name].weights = graph.nodes[node].weights + 1;
			}
		}
	}
	FILE* f = fopen(filename, "w");
	if (f == NULL)
		return;

	for (int i = 1; i <= graph.numNodes; i++) {
		fprintf(f, "%d ", graph.nodes[i].weights);
	}
	fclose(f);
}

int main()
{
	int s;
	graphVertex graph = readGraphVertex("bfs.in", &s);
	bfs_search(graph, s, "bfs.out");
}