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

typedef struct edge {
	int leftNode;
	int rightNode;
} edge;

typedef struct graphEdges {
	edge* edges;
	int numNodes;
	int numEdges;
} graphEdges;

graphEdges readGraphEdgeList(const char* fileName, int* start)
{
	graphEdges graph{};

	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;

	fscanf(f, "%d%d%d", &(graph.numNodes), &(graph.numEdges), start);
	int k = 0;
	graph.edges = (edge*)malloc(graph.numEdges * sizeof(edge));

	for (int i = 0; i < graph.numEdges; i++) {
		fscanf(f, "%d", &(graph.edges[k].leftNode));
		fscanf(f, "%d", &(graph.edges[k].rightNode));
		k++;
	}
	fclose(f);
	return graph;
}

int queue[1000];
int indexQueue = 0;

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

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

void bfs_edges(graphEdges graph, int startNode, int* visited, int* poz)
{
	int t = 0, i, k, ok;
	int n = 0;
	push(startNode);
	visited[startNode] = -1;
	poz[startNode] = t;
	while (indexQueue != 0) {
		startNode = pop();
		if (visited[startNode] == -1)
			t++;
		k = 0;
		ok = 1;
		for (i = 0; i < graph.numEdges; i++)
		{
			if (graph.edges[i].leftNode == startNode)
			{
				if (visited[graph.edges[i].rightNode] == 0) {
					ok = 0;
					push(graph.edges[i].rightNode);
					poz[graph.edges[i].rightNode] = t;
					if (n == 1)
					{
						n = 0;
						visited[graph.edges[i].rightNode] = -1;
					}
					else
					{
						if (k == 0 && visited[startNode] == -1)
						{
							k = 1;
							visited[graph.edges[i].rightNode] = -1;
						}
						else
							visited[graph.edges[i].rightNode] = 1;
					}
				}
			}
		}
		if (ok == 1 && visited[startNode] == -1)
			n = 1;
	}
}

int main()
{
	int start;
	graphEdges graphE = readGraphEdgeList("bfs.in", &start);
	int* visited = (int*)calloc((graphE.numNodes + 1), sizeof(int));
	int* poz = (int*)malloc((graphE.numNodes + 1) * sizeof(int));
	bfs_edges(graphE, start, visited, poz);
	FILE* f = fopen("bfs.out", "w");
	for (int i = 1; i <= graphE.numNodes; i++)
	{
		if (poz[i] < 0)
			poz[i] = -1;
		fprintf(f, "%d ", poz[i]);
	}
	fclose(f);
	return 0;
}