#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct vertex {
	int cost;
	int name;
	struct vertex **neighbours;
	int numNeighbours;
} vertex;

typedef struct graphVertex {
	int numEdges;
	int numNodes;
	int sourceNode;
	vertex *nodes;
} graphVertex;

int queue[100];
int queueIndex = 0;

void push(int value)
{
	if (queueIndex < 100) {
		queue[queueIndex] = value;
		queueIndex++;
	} else
		printf("QUEUE IS FULL");
}
int pop()
{
	if (queueIndex > 0) {
		int poppedValue = queue[0];
		for (int i = 0; i < queueIndex; i++)
			queue[i] = queue[i + 1];
		queueIndex--;
		return poppedValue;
	} else {
		printf("QUEUE IS EMPTY!");
		return 0;
	}
}
graphVertex readGraph(const char *filename)
{
	FILE *f = fopen(filename, "r");
	graphVertex newGraph;
	int leftNode, rightNode;
	newGraph.nodes = NULL;
	newGraph.numEdges = 0;
	newGraph.numNodes = 0;
	newGraph.sourceNode = 0;
	fscanf(f, "%d %d %d", &(newGraph.numNodes), &(newGraph.numEdges), &(newGraph.sourceNode));
	newGraph.nodes = (vertex *)malloc(sizeof(vertex) * newGraph.numNodes);
	for (int i = 0; i < newGraph.numNodes; i++) {
		newGraph.nodes[i].cost = -1;
		newGraph.nodes[i].name = i + 1;
		newGraph.nodes[i].neighbours = NULL;
		newGraph.nodes[i].numNeighbours = 0;
	}
	newGraph.nodes[(newGraph.sourceNode - 1)].cost = 0;
	for (int i = 0; i < newGraph.numEdges; i++) {
		fscanf(f, "%d %d", &leftNode, &rightNode);
		newGraph.nodes[leftNode - 1].neighbours = (vertex **)realloc(newGraph.nodes[leftNode - 1].neighbours, sizeof(vertex *) * (newGraph.nodes[leftNode - 1].numNeighbours + 1));
		newGraph.nodes[leftNode - 1].neighbours[newGraph.nodes[leftNode - 1].numNeighbours] = &newGraph.nodes[rightNode - 1];
		newGraph.nodes[leftNode - 1].numNeighbours++;
	}
	return newGraph;
}
void calculateCost(graphVertex Graph)
{
	int poppedNode;
	int *visited = (int *)calloc(Graph.numNodes, sizeof(int));
	push(Graph.sourceNode);
	while (queueIndex > 0) {
		poppedNode = pop();
		for (int i = 0; i < Graph.nodes[poppedNode - 1].numNeighbours; i++) {
			if (visited[Graph.nodes[poppedNode - 1].neighbours[i]->name - 1] == 0 && (Graph.nodes[poppedNode - 1].neighbours[i]->cost > (Graph.nodes[poppedNode - 1].cost + 1) || Graph.nodes[poppedNode - 1].neighbours[i]->cost == -1)) {
				Graph.nodes[poppedNode - 1].neighbours[i]->cost = Graph.nodes[poppedNode - 1].cost + 1;
				push(Graph.nodes[poppedNode - 1].neighbours[i]->name);
			}
			visited[poppedNode - 1] = 1;
		}
	}
}
void printCost(graphVertex Graph, const char *filename)
{
	FILE *f = fopen(filename, "w");
	for (int i = 0; i < Graph.numNodes; i++) {
		fprintf(f, "%d ", Graph.nodes[i].cost);
	}
	fclose(f);
}
int main()
{
	graphVertex NewGraph = readGraph("bfs.in");
	calculateCost(NewGraph);
	printCost(NewGraph, "bfs.out");
}