#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

int front;

void push(int value)

{
	stack[indexStack++] = value;
}

int pop()

{
	front++;

	return stack[front - 1];
}

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 > front) {
		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;
}