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

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

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

int *minPath;
int* vizited;
int* queue;
int indexQueue;

void push(int numNodes, int value)
{
	if (indexQueue < numNodes + 1)
		queue[indexQueue++] = value;
	else
		printf("Dimensiune coada depasita!");
}

int pop()
{
	if (indexQueue > 0)
	{
		int value = queue[0];
		for (int i = 0; i < indexQueue ; i++)
			queue[i] = queue[i + 1];
		queue[indexQueue] = 0;
		indexQueue--;
		return value;
	}
	printf("Coada goala!");
	return -1;
}

graphVertex* readFile(const char* filename, int *startNode)
{
	FILE* f = fopen(filename, "r");
	if (f == NULL)
	{
		printf("Eroare la deschiderea fisierului!");
		exit(-1);
	}
	graphVertex* graph = (graphVertex*)malloc(sizeof(graphVertex));
	fscanf(f, "%d%d%d", &graph->numNodes, &graph->numEdges, startNode);
	graph->nodes = (vertex*)malloc(graph->numNodes * sizeof(vertex));
	int i, leftNode, rightNode;
	for (i = 0; i < graph->numNodes; i++)
	{
		graph->nodes[i].name = i;
		graph->nodes[i].numNeighbors = 0;
		graph->nodes[i].neighbors = (vertex**)malloc(graph->numNodes*sizeof(vertex*));
	}
	for (i = 0; i < graph->numEdges; i++)
	{
		fscanf(f, "%d%d", &leftNode, &rightNode);
		if (leftNode != rightNode)
		{
		graph->nodes[leftNode-1].numNeighbors++;
		graph->nodes[leftNode-1].neighbors[graph->nodes[leftNode-1].numNeighbors - 1] = &graph->nodes[rightNode-1];
		}
	}
	fclose(f);
	return graph;
}

void getAllMinPath(graphVertex *graph, int startNode)
{
	int i;
	vizited[startNode] = 1;
	for (i = 0; i < graph->nodes[startNode].numNeighbors; i++)
	{
		if (minPath[graph->nodes[startNode].neighbors[i]->name] == -1 || minPath[graph->nodes[startNode].neighbors[i]->name] > minPath[startNode] + 1)
			minPath[graph->nodes[startNode].neighbors[i]->name] = minPath[startNode] + 1;
		if(vizited[graph->nodes[startNode].neighbors[i]->name]==0)
			push(graph->numNodes, graph->nodes[startNode].neighbors[i]->name);
		else
			vizited[graph->nodes[startNode].neighbors[i]->name] = 1;
	}
	while (indexQueue > 0)
		getAllMinPath(graph, pop());
}

int main()
{
	int startNode, i;
	graphVertex* graph = (graphVertex*)malloc(sizeof(graphVertex));
	graph->nodes = NULL;
	graph->numNodes = 0;
	graph->numEdges = 0;
	graph=readFile("bfs.in", &startNode);
	startNode--;
	minPath = (int*)malloc(graph->numNodes * sizeof(int));
	queue = (int*)malloc(graph->numNodes * sizeof(int));
	vizited = (int*)malloc(graph->numNodes * sizeof(int));
	for (i = 0; i < graph->numNodes; i++)
	{
		minPath[i] = -1;
		vizited[i] = 0;
	}
	minPath[startNode] = 0;
	getAllMinPath(graph, startNode);
	FILE* g = fopen("bfs.out", "w");
	for (i = 0; i < graph->numNodes; i++)
		fprintf(g, "%d ", minPath[i]);
	return 0;
}