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

void bfs(graphEdges graph, int startNode)
{
	int queue[100], i = 0, j = 0, costCt = 0, ct;
	int visited[100] = {0}, cost[100] = {0};
	queue[j] = startNode;
	while (i <= j) {
		visited[queue[i]] = 1;
		printf("%d ", queue[i]);
		for (int k = 1; k < graph.numEdges; k++) {
			if (graph.edges[k].leftNode == queue[i] && visited[graph.edges[k].rightNode] == 0) {
				ct = 0;
				for (int l = i + 1; l <= j; l++) {
					if (queue[l] == graph.edges[k].rightNode) ct = 1;
				}

				if (ct == 0) {
					if (i == j) costCt++;
					queue[++j] = graph.edges[k].rightNode;
					cost[graph.edges[k].rightNode] = cost[queue[i]] + 1;
				}
			}
		}
		i++;
	}
	for (int i = 1; i <= graph.numNodes; i++) {
		if (visited[i] == 0) cost[i] = -1;
	}
	FILE* o = fopen("bfs.out", "w");
	if (o == NULL) return;
	for (int i = 1; i <= graph.numNodes; i++) {
		fprintf(o, "%d ", cost[i]);
	}
	printf("\n");
}

graphEdges readGraphEdgeList(const char* fileName, int* start)
{
	graphEdges graph;
	graph.numEdges = 0;
	graph.edges = NULL;
	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;
	fscanf(f, "%d %d %d\n", &(graph.numNodes), &(graph.numEdges), start);
	graph.edges = (edge*)malloc(sizeof(edge) * graph.numEdges);
	int a, b;
	for (int i = 0; i < graph.numEdges; i++) {
		fscanf(f, "%d %d\n", &a, &b);
		graph.edges[i].leftNode = a;
		graph.edges[i].rightNode = b;
	}
	//TODO

	fclose(f);
	return graph;
}

int main()
{
	int start;
	graphEdges graphE = readGraphEdgeList("bfs.in", &start);
	bfs(graphE, start);
	return 0;
}