#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef struct graphEdges {
	int node;
	int cost;
	int* neighbors;
	int nr_neighbors;
} graphEdges;

int N, M;

int queue[1000001];
int indexQueue = 1;

void push(int value)
{
		queue[indexQueue++] = value;
}

/*int pop()
{
	int value = queue[0];
	for (int i = 0; i < indexQueue - 1; i++)
		queue[i] = queue[i + 1];
	queue[indexQueue - 1] = 0;
	indexQueue--;
	return value;
}*/

graphEdges* readGraphEdgeList(const char* fileName, int* start)
{
	FILE* f = fopen(fileName, "r");
	fscanf(f, "%d%d%d", &N, &M, start);
	graphEdges* graph=(graphEdges*)malloc((N+1)*sizeof(graphEdges));

	for (int i = 1; i <= N; i++)
	{
		graph[i].node = i;
		graph[i].cost = -1;
		graph[i].nr_neighbors = 0;
		graph[i].neighbors = NULL;
	}
	int left, right;
	for (int i = 0; i < M; i++) {
		fscanf(f, "%d%d", &left,&right);
		graph[left].nr_neighbors++;
		graph[left].neighbors = (int*)realloc(graph[left].neighbors, (graph[left].nr_neighbors + 1) * sizeof(int));
		graph[left].neighbors[graph[left].nr_neighbors - 1] = right;
	}
	fclose(f);
	return graph;
}

void bfs_edges(graphEdges* graph, int startNode)
{
	push(startNode);
	graph[startNode].cost = 0;
	for (int i = 1; i < indexQueue; i++)
		for (int j = 0; j < graph[queue[i]].nr_neighbors; j++)
			if (graph[graph[queue[i]].neighbors[j]].cost == -1)
			{
				push(graph[queue[i]].neighbors[j]);
				graph[queue[indexQueue-1]].cost = graph[queue[i]].cost + 1;
			}
}

int main()
{
	int start;
	graphEdges* graphE = readGraphEdgeList("bfs.in", &start);
	bfs_edges(graphE, start);
	FILE* f = fopen("bfs.out", "w");
	for (int i = 1; i <= N; i++)
		fprintf(f, "%d ", graphE[i].cost);
	fclose(f);
	return 0;
}