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

typedef struct vertex {
	int name;
	int* neighbors;
	int numNeighbors;
	int level;
} vertex;

int n, m, s;
int stack[100005];
int indexStack = 0;
//am cam facut din stiva coada
void push(int value)
{
	if (indexStack < 100) {
		for (int i = indexStack; i > 0; i--)
			stack[i] = stack[i - 1];
		stack[0] = value;
		indexStack++;
	} 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_pointers(vertex* graph, int startNode)
{
	for (int i = 1; i <= graph[startNode].numNeighbors; i++) {
		if (graph[graph[startNode].neighbors[i - 1]].level == -1) {
			graph[graph[startNode].neighbors[i - 1]].level = graph[startNode].level + 1;
			push(graph[startNode].neighbors[i - 1]);
		}
	}
	if (indexStack > 0) {
		int w = pop();
		bfs_pointers(graph, w);
	}
}

vertex* readGraphVertex(const char* fileName)
{
	FILE* f = fopen(fileName, "r");
	fscanf(f, "%i%i%i", &n, &m, &s);
	vertex* graph = (vertex*)malloc(sizeof(vertex) * (n + 1));
	if (f == NULL)
		return graph;
	if (graph == NULL)
		return graph;
	for (int i = 1; i <= n; i++) {
		graph[i].name = i;
		graph[i].numNeighbors = 0;
		graph[i].neighbors = NULL;
		graph[i].level = -1;
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		fscanf(f, "%i%i", &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;
}

int main()
{
	vertex* graphV = readGraphVertex("bfs.in");
	graphV[s].level = 0;
	bfs_pointers(graphV, s);
	FILE* g = fopen("bfs.out", "w");
	for (int i = 1; i <= n; i++)
		fprintf(g, "%d ", graphV[i].level);
	fclose(g);
	/*for (int i = 1; i <= n; i++)
		printf("%d ", graphV[i].level);*/
	return 0;
}