#define _CRT_SECURE_NO_WARNINGS
#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;
} graphEdges;

typedef struct distance {
	int name;
	int distance;
} distance;

int stack[100];
int indexStack = 0;

void push(int value)
{
	if (indexStack < 100)
		stack[indexStack++] = value;
	else
		printf("Dimensiune stiva depasita!\n");
}

int pop()
{
	// verificare daca sunt elemente in stiva
	if (indexStack > 0) {
		int value = stack[--indexStack];
		stack[indexStack] = 0;
		return value;
	}
	printf("Stiva este goala!\n");
	return (int)0;
}
int pop_coada()
{
	if (indexStack > 0) {
		int value = stack[0];
		for (int i = 0; i < indexStack - 1; i++)
			stack[i] = stack[i + 1];
		stack[indexStack] = 0;
		indexStack--;
		return value;
	}
	printf("Coada este goala!\n");
	return (int)0;
}
graphEdges readGraphEdgeList(const char* fileName)
{
	graphEdges graph;
	graph.numEdges = 0;
	graph.edges = NULL;
	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;
	char s[10];
	fscanf(f, "%s", s);
	graph.numNodes = atoi(s);
	fscanf(f, "%s", s);
	graph.numEdges = atoi(s);
	fscanf(f, "%s", s);
	graph.edges = (edge*)malloc(graph.numEdges * sizeof(edge));
	for (int i = 0; i < graph.numEdges; i++) {
		fscanf(f, "%s", s);
		graph.edges[i].leftNode = atoi(s);
		fscanf(f, "%s", s);
		graph.edges[i].rightNode = atoi(s);
	}
	fclose(f);
	return graph;
}
void bfs_edges(graphEdges graph, int startNode, int* visited, const char filename)
{
	if (startNode > graph.numNodes) {
		printf("The node %d doesn't exist", startNode);
		return;
	}
	push(startNode);
	visited[startNode] = 1;
	int dist = 0;
	int* distance = (int*)malloc(graph.numNodes * sizeof(int));
	while (indexStack > 0) {
		int j = pop_coada();
		distance[j] = dist;
		dist++;
		for (int i = 0; i < graph.numEdges; i++)
			if (j == graph.edges[i].leftNode && visited[graph.edges[i].rightNode] == 0) {
				push(graph.edges[i].rightNode);
				visited[graph.edges[i].rightNode] = 1;
			}
	}
	for (int i = 0; i < graph.numNodes; i++)
		if (visited[i] == 0)
			distance[i] = 0;

	FILE* g = fopen(filename, "r");
	if (g == NULL)
		exit(-1);
	for (int i = 0; i < graph.numNodes; i++)
		fprintf(g, "%d ", distance[i]);
	fclose(g);
}
int main()
{
	graphEdges newGraph = readGraphEdgeList("bfs.in");
	FILE* f = fopen("bfs.in", "r");
	if (f == NULL)
		exit(-1);
	char s[10];
	fscanf(f, "%s", s);
	fscanf(f, "%s", s);
	fscanf(f, "%s", s);
	fclose(f);
	int node = atoi(s);
	int visited[100] = {0};
	bfs_edges(newGraph, node, visited, "bfs.out");
	return 0;
}