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

/*typedef struct vertex {
	int name;
	struct vertex** neighbors;
	int numNeighbors;
	int weights;
} vertex;

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

int queue[100001];
int indexQueue = 0;

typedef struct vertex {
	int numNeighbors;
	int* neighbors;
	int name;
	int weights;
} vertex;
int numNodes, numEdges, root;

int source;
vertex* readGraphVertex(const char* fileName)
{
	vertex* graph;

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

	fscanf(f, "%i%i%i", &numNodes, &numEdges, &source);
	graph = (vertex*)malloc(sizeof(vertex) * (numNodes + 1));
	if (graph == NULL)
		return graph;
	for (int i = 1; i <= numNodes; i++) {
		graph[i].name = i;
		graph[i].numNeighbors = 0;
		graph[i].weights = -1;
		graph[i].neighbors = NULL;
	}
	int x, y;
	for (int i = 0; i < numEdges; i++) {  //
		fscanf(f, "%d%d", &x, &y);

		graph[x].numNeighbors++;
		graph[x].neighbors = (int*)realloc(graph[x].neighbors, (graph[x].numNeighbors + 1) * sizeof(int));
		graph[x].neighbors[graph[x].numNeighbors - 1] = y;
	}
	fclose(f);
	return graph;
}

void bfs_vertex(vertex* graph, int startNode)
{
	graph[startNode].weights = 0;
	int n = 1;
	queue[n] = startNode;
	int m = 1;
	while (m <= n) {
		int value = queue[m];
		m++;
		for (int i = 0; i < graph[value].numNeighbors; i++)
			if (graph[graph[value].neighbors[i]].weights == -1) {
				n++;
				queue[n] = graph[graph[value].neighbors[i]].name;
				graph[graph[value].neighbors[i]].weights = 1 + graph[value].weights;
			}
	}
	FILE* g = fopen("bfs.out", "w");
	for (int i = 1; i <= numNodes; i++) {
		fprintf(g, "%d ", graph[i].weights);
	}
}

int main(int argc, char** argv)
{
	vertex* graph = readGraphVertex("bfs.in");
	bfs_vertex(graph, source);
}