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

#define Q_SIZE 100000

int N, M, S;

int queue[Q_SIZE];

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)
{
	int up = 0, down = 0;
	graphV[startNode].cost = 0;
	queue[up++] = startNode;
	while (up - down) {
		int node = queue[down++];
		for (int i = 0; i < graphV[node].numNeighbours; i++) {
			if (graphV[graphV[node].neighbours[i]].cost == -1) {
				queue[up++] = 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;
}