#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 dfs_edges(graphEdges graph, int currentNode, int* visited, FILE* f)
{
	if (currentNode > graph.numNodes) {
		printf("The node %d doesn't exist", currentNode);
		return;
	}
	push(currentNode);
	visited[currentNode] = 1;
	int dist = 0, j = 0;
	int d[100] = {0};
	int marcator = 0;
	while (indexStack > 0) {
		if (j != currentNode)
			marcator = 0;
		j = pop();
		d[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;
				marcator = i;
				break;
			}
		if (indexStack == 0) {
			dist = 1;
			for (int i = marcator; i < graph.numEdges; i++)
				if (visited[graph.edges[i].rightNode] == 0 && currentNode == graph.edges[i].leftNode) {
					push(graph.edges[i].rightNode);
					visited[graph.edges[i].rightNode] = 1;
					break;
				}
		}
	}
	for (int i = 1; i <= graph.numNodes; i++)
		if (visited[i] == 0) {
			d[i] = -1;
		}
	// fprintf(f, "Distanta de la %d la celelalte noduri este:\n", currentNode);
	for (int i = 1; i <= graph.numNodes; i++)
		fprintf(f, "%d ", d[i]);
}
void printEdges(graphEdges graph)
{
	for (int i = 0; i < graph.numEdges; i++)
		printf("[%d %d]\n", graph.edges[i].leftNode, graph.edges[i].rightNode);
}

int main()
{
	graphEdges newGraph = readGraphEdgeList("bfs.in.txt");
	// printEdges(newGraph);
	int s;
	FILE* f = fopen("bfs.in.txt", "r");
	if (f == NULL)
		return 0;
	fscanf(f, "%d", &s);
	fscanf(f, "%d", &s);
	fscanf(f, "%d", &s);
	fclose(f);
	int visited[100] = {0};
	FILE* g = fopen("bfs.out.txt", "w");
	if (g == NULL)
		return 0;

	dfs_edges(newGraph, s, visited, g);
	fclose(g);
	return 0;
}