#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct edge {
	int leftNode;
	int rightNode;
} edge;

typedef struct graphEdges {
	edge* edges;
	int numNodes;
	int numEdges;
	int root;
} graphEdges;
graphEdges readGraphEdgeList(const char* fileName)
{
	graphEdges graph;
	graph.numEdges = 0;
	graph.edges = NULL;
	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;
	//TODO
	fscanf(f, "%i", &graph.numNodes);
	fscanf(f, "%i", &graph.numEdges);
	fscanf(f, "%i\n", &graph.root);
	int i = 0;
	char sir[200];
	graph.edges = (edge*)malloc(graph.numEdges * sizeof(edge));
	while (fgets(sir, 200, f)) {
		char* p = strtok(sir, " \r\n");
		if (p != NULL) {
			graph.edges[i].leftNode = atoi(p);
			p = strtok(NULL, " \r\n");
			graph.edges[i].rightNode = atoi(p);
			i++;
		}
	}
	if (i > graph.numEdges) {
		printf("Prea multe muchii in fisier");
		exit(0);
	}
	fclose(f);
	return graph;
}
int queue[100000];
int indexQueue = 0;
void pushqueue(int value)
{
	if (indexQueue < 100000)
		queue[indexQueue++] = value;
	else
		printf("Dimensiune coada depasita!\n");
}

int popqueue()
{
	//verificare daca sunt elemente in stiva
	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(graphEdges graph, int startnode, int* visited)
{
	visited[startnode] = 0;
	pushqueue(startnode);
	while (indexQueue) {
		int value = popqueue();
		for (int i = 0; i < graph.numEdges; i++)
			if (graph.edges[i].leftNode == value)
				if (visited[graph.edges[i].rightNode] == -1) {
					visited[graph.edges[i].rightNode] = 1 + visited[graph.edges[i].leftNode];
					pushqueue(graph.edges[i].rightNode);
				}
	}
}
int main()
{
	int visited[100001];
	graphEdges graph = readGraphEdgeList("bfs.in");
	for (int i = 1; i <= graph.numNodes; i++)
		visited[i] = -1;
	bfs(graph, graph.root, visited);
	FILE* f = fopen("bfs.out", "w");
	for (int i = 1; i <= graph.numNodes; i++)
		fprintf(f, "%i ", visited[i]);
	fclose(f);
}