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

#define Q_SIZE 100000
#define COST_VECTOR_SIZE 100000

int queue[Q_SIZE];
int indexQueue = 0;

void push(int value)
{
	if (indexQueue < Q_SIZE)
		queue[indexQueue++] = value;
	else
		printf("Dimensiune coada depasita!\n");
}

int pop()
{
	if (indexQueue > 0) {
		int value = queue[0];
		for (int i = 0; i < indexQueue - 1; i++) {
			queue[i] = queue[i + 1];
		}
		queue[indexQueue--] = 0;
		return value;
	}
	printf("Coada este goala!\n");
	return (int)0;
}

int N, M, S;
int cost[COST_VECTOR_SIZE] = {-1};

typedef struct graph {
	int name;
	int numNeighbours;
	int* neighbours;
	int cost;
} graph;

graph* read(const char* filename)
{
	FILE* f = fopen(filename, "r");
	if (f == NULL) {
		return NULL;
	}
	fscanf(f, "%d %d %d", &N, &M, &S);
	graph* newGraph = (graph*)malloc(sizeof(graph) * (N + 1));

	for (int i = 1; i <= N; i++) {
		newGraph[i].name = i;
		newGraph[i].numNeighbours = 0;
		newGraph[i].neighbours = NULL;
		newGraph[i].cost = -1;
	}

	int left, right;
	for (int i = 0; i < M; i++) {
		fscanf(f, "%d %d", &left, &right);
		newGraph[left].numNeighbours++;
		newGraph[left].neighbours = (int*)realloc(newGraph[left].neighbours, sizeof(int) * newGraph[left].numNeighbours);
		newGraph[left].neighbours[newGraph[left].numNeighbours - 1] = right;
	}

	fclose(f);
	return newGraph;
}

void BFS(graph* graphV, int startNode)
{
	graphV[startNode].cost = 0;
	push(startNode);
	while (indexQueue) {
		int node = pop();
		for (int i = 0; i < graphV[node].numNeighbours; i++) {
			if (graphV[graphV[node].neighbours[i]].cost == -1) {
				push(graphV[graphV[node].neighbours[i]].name);
				graphV[graphV[node].neighbours[i]].cost = 1 + graphV[node].cost;
			}
		}
	}
}

int main()
{
	graph* graphV = read("bfs.in");

	BFS(graphV, S);

	FILE* f = fopen("bfs.out", "w");
	for (int i = 1; i <= N; i++) {
		fprintf(f, "%d ", graphV[i].cost);
	}
	fclose(f);

	return 0;
}