#define _CRT_SECURE_NO_WARNINGS
#define size 1000000
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct vertex
{
	int num;
	int* canGo;
}vertex;
typedef struct GraphVertex
{
	int numNodes;
	int numEdges;
	vertex* nodes;

}GraphVertex;
int queue[size];
int queueIndex = 0;
int visited[size] = { 0 };
int cost[size];
void enqueue(int value)
{
	if (queueIndex < size)
		queue[queueIndex++] = value;
	else
		return;
}

int dequeue()
{
	if (queueIndex == 0) {
		printf("Coada este goala");
		return -1;
	}
	int value = queue[0];
	for (int i = 0; i < queueIndex - 1; i++)
		queue[i] = queue[i + 1];
	queueIndex--;

	return value;
}
GraphVertex readFile(const char* fname,int *source)
{
	GraphVertex graph;
	graph.nodes = NULL;

	FILE* fptr = fopen(fname, "r");
	

	int numNodes, edges, s;
	fscanf(fptr, "%d %d %d", &numNodes, &edges, &s);
	*source = s;
	graph.nodes = (vertex*)malloc(numNodes * sizeof(vertex));
	for (int i = 0; i < numNodes; i++)
	{
		graph.nodes[i].canGo = NULL;
		graph.nodes[i].num = 0;
	}
	graph.numEdges = edges;
	graph.numNodes = numNodes;
	int left,right;
	while (edges)
	{
		fscanf(fptr, "%d %d", &left, &right);
		graph.nodes[left-1].canGo = (int*)realloc(graph.nodes[left-1].canGo, (graph.nodes[left-1].num + 1) * sizeof(int));
		graph.nodes[left-1].canGo[graph.nodes[left-1].num] = right;
		graph.nodes[left-1].num++;
		edges--;
	}

	fclose(fptr);
	return graph;
}

void bfs(GraphVertex graph,int source)
{
	enqueue(source);
	cost[source] = 0;
		while (queueIndex)
		{
			int current = dequeue();
			visited[current] = 1;
			for (int i = 0; i < graph.nodes[current-1].num; i++)
			{
				if (!visited[graph.nodes[current-1].canGo[i]])
				{
					visited[graph.nodes[current-1].canGo[i]] = 2;
					cost[graph.nodes[current-1].canGo[i]] = cost[current] + 1;
					enqueue(graph.nodes[current-1].canGo[i]);
				}
			}
	}
}
void print_out(GraphVertex graph)
{
	FILE* fptr = fopen("bfs.out", "w");
	for (int i = 1; i < graph.numNodes+1; i++)
		fprintf(fptr,"%d ", cost[i]);

	fclose(fptr);
}
int main()
{
	memset(cost, -1, 4*size);
	int source;
	GraphVertex graph=readFile("bfs.in", &source);
	bfs(graph, source);
	print_out(graph);
	return 0;
}