#define _CRT_SECURE_NO_WARNINGS

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

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

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

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

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

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;
}

void bfs_edges(graphEdges graph, int n, int startNode, int* visited)
{
	int C[10001];
	int* D = NULL;
	int p, u, x;
	p = u = 1;
	C[1] = startNode;
	D = (int*)calloc(n, sizeof(int));
	D[startNode] = 0;
	visited[startNode] = 1;
	int d = 1;
	int ok = 0;
	while (p <= u)
	{
		ok = 0;
		x = C[p];
		for (int i = 0; i <= graph.numEdges; i++)
		{
			if (graph.edges[i].leftNode == x && visited[graph.edges[i].rightNode] == 0)
			{
				ok = 1;
				D[graph.edges[i].rightNode] = d;
				u++;
				C[u] = graph.edges[i].rightNode;
				visited[graph.edges[i].rightNode] = 1;
			}
		}
		if(ok == 1)
			d++;
		p++;
	}
	for (int i = 0; i < n; i++)
		if (D[i] == 0 && i != startNode)
			D[i] = -1;
	FILE* g = fopen("bfs.out", "w");
	for (int i = 1; i <= n; i++)
		fprintf(g, "%d ", D[i]);
	fclose(g);
		//printf("%d %d\n", C[i], D[i]);
}

graphEdges readGraphEdgeList(const char* fileName, int* S)
{
	graphEdges graph;
	graph.numEdges = 0;
	graph.edges = NULL;
	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;

	//TODO

	int n = 0;
	fscanf(f, "%d", &n);
	graph.numNodes = n;

	int m = 0;
	fscanf(f, "%d", &m);
	graph.numEdges = m;

	int s = 0;
	fscanf(f, "%d", &s);
	*S = s;

	graph.edges = (edge*)malloc(m * sizeof(edge));
	//int no = 0;
	for (int i = 0; i < graph.numEdges; i++)
	{
		int auxi = 0;
		int auxj = 0;
		fscanf(f, "%d", &auxi);
		fscanf(f, "%d", &auxj);
		//graph.edges = (edge*)realloc(graph.edges, (m + 1) * sizeof(edge));
		graph.edges[i].leftNode = auxi;
		graph.edges[i].rightNode = auxj;
		//m++;
	}
	//graph.numEdges = m;

	fclose(f);
	return graph;
}

int main()
{
	//EDGES
	int S = 0;
	graphEdges graphE = readGraphEdgeList("bfs.in", &S);
	int visited3[10001] = { 0 };  //we assume fewer than 100 nodes
	bfs_edges(graphE, graphE.numNodes, S, visited3);
	printf("\n");

	return 0;
}