#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;
	int sursa;
} graphEdges;

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

int stack[100005];
int indexStack = 0;

void push(int value)
{
	if (indexStack < 100)
		stack[indexStack++] = value;
	else
		printf("Dimensiune stiva depasita!\n");
}
int pop_coada()
{
	if (indexStack > 0) {
		int value = stack[0];
		for (int i = 0; i < indexStack - 1; i++)
			stack[i] = stack[i + 1];
		indexStack--;
		return value;
	}
	printf("Coada este goala!\n");
	return 0;
}
graphEdges readGraphEdgeList(const char* fileName)
{
	graphEdges graph;
	FILE* f = fopen(fileName, "r");
	fscanf(f, "%d %d %d", &graph.numNodes, &graph.numEdges, &graph.sursa);
	graph.edges = (edge*)malloc(graph.numEdges * sizeof(edge));
	for (int i = 0; i < graph.numEdges; i++)
		fscanf(f, "%d %d", &graph.edges[i].leftNode, &graph.edges[i].rightNode);
	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 + 1) * 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;
				break;
			}
		if (indexStack == 0) {
			dist = 1;
			for (int i = 0; i < graph.numEdges; i++)
				if (startNode == graph.edges[i].leftNode && visited[graph.edges[i].rightNode] == 0) {
					push(graph.edges[i].rightNode);
					visited[graph.edges[i].rightNode] = 1;
					break;
				}
		}
	}
	for (int i = 1; i <= graph.numNodes; i++)
		if (visited[i] == 0)
			distance[i] = -1;

	FILE* g = fopen(filename, "w");
	if (g == NULL)
		exit(-1);
	for (int i = 1; i <= graph.numNodes; i++)
		fprintf(g, "%d ", distance[i]);
	fclose(g);
}

int main()
{
	graphEdges newGraph = readGraphEdgeList("bfs.in");
	int visited[100] = {0};
	bfs_edges(newGraph, newGraph.sursa, visited, "bfs.out");
	return 0;
}