#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;
	int root;
	vertex* nodes;
} graphVertex;
graphVertex readGraphVertex(const char* fileName)
{
	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), &(graph.root));
	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 stanga, dreapta;
	for (int i = 0; i < graph.numEdges; i++) {
		fscanf(f, "\n%i%i", &stanga, &dreapta);
		if (graph.nodes[stanga].numNeighbors == 0)
			graph.nodes[stanga].neighbors = (vertex**)malloc(sizeof(vertex*));
		else
			graph.nodes[stanga].neighbors = (vertex**)realloc(graph.nodes[stanga].neighbors, (graph.nodes[stanga].numNeighbors + 1) * sizeof(vertex*));
		graph.nodes[stanga].neighbors[graph.nodes[stanga].numNeighbors] = (vertex*)malloc(sizeof(vertex));
		graph.nodes[stanga].neighbors[graph.nodes[stanga].numNeighbors] = &graph.nodes[dreapta];
		graph.nodes[stanga].numNeighbors++;
	}
	fclose(f);
	return graph;
}
int queue[100001];
int indexQueue = 0;
void pushqueue(int value)
{
	if (indexQueue < 100001)
		queue[indexQueue++] = value;
	else
		printf("Dimensiune coada depasita!\n");
}

int popqueue()
{
	if (indexQueue > 0) {
		int value = queue[0];
		for (int i = 1; i < indexQueue; i++)
			queue[i - 1] = queue[i];
		indexQueue--;

		return value;
	}
	printf("Coada este goala!\n");
	return (int)0;
}
void bfs(graphVertex graph, int startnode)
{
	graph.nodes[startnode].weights = 0;
	pushqueue(startnode);
	while (indexQueue) {
		int value = popqueue();
		for (int i = 0; i < graph.nodes[value].numNeighbors; i++)
			if (graph.nodes[value].neighbors[i]->weights == -1) {
				pushqueue(graph.nodes[value].neighbors[i]->name);
				graph.nodes[value].neighbors[i]->weights = 1 + graph.nodes[value].weights;
			}
	}
}
int main()
{
	graphVertex graph = readGraphVertex("bfs.in");
	bfs(graph, graph.root);
	FILE* f = fopen("bfs.out", "w");
	for (int i = 1; i <= graph.numNodes; i++)
		fprintf(f, "%i ", graph.nodes[i].weights);
	fclose(f);
}