#define _CRT_SECURE_NO_WARNINGS
#define size 1000000
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct vertex
{
	int num;
	int* canGo;
}vertex;
typedef struct GraphVertex
{
	int numNodes;
	int numEdges;
	vertex* nodes;

}GraphVertex;
int queue[size];
int queueIndex = 0;
int visited[size] = { 0 };
int cost[size];
int f;
int l;
GraphVertex readFile(const char* fname, int* source)
{
	GraphVertex graph;
	graph.nodes = NULL;

	FILE* fptr = fopen(fname, "r");


	int numNodes, edges, s;
	fscanf(fptr, "%d %d %d", &numNodes, &edges, &s);
	*source = s;
	graph.nodes = (vertex*)malloc(numNodes * sizeof(vertex));
	for (int i = 0; i < numNodes; i++)
	{
		graph.nodes[i].canGo = NULL;
		graph.nodes[i].num = 0;
	}
	graph.numEdges = edges;
	graph.numNodes = numNodes;
	int left, right;
	while (edges)
	{
		fscanf(fptr, "%d %d", &left, &right);
		graph.nodes[left - 1].canGo = (int*)realloc(graph.nodes[left - 1].canGo, (graph.nodes[left - 1].num + 1) * sizeof(int));
		graph.nodes[left - 1].canGo[graph.nodes[left - 1].num] = right;
		graph.nodes[left - 1].num++;
		edges--;
	}

	fclose(fptr);
	return graph;
}

void bfs(GraphVertex graph, int source)
{
	queue[f] = source;
	l++;
	cost[source] = 0;
	while (l!=f)
	{
		int current = queue[f];
		f++;
		visited[current] = 1;
		for (int i = 0; i < graph.nodes[current - 1].num; i++)
		{
			if (!visited[graph.nodes[current - 1].canGo[i]])
			{
				visited[graph.nodes[current - 1].canGo[i]] = 2;
				cost[graph.nodes[current - 1].canGo[i]] = cost[current] + 1;
				queue[l] = graph.nodes[current - 1].canGo[i];
				l++;
			}
		}
	}
}
void print_out(GraphVertex graph)
{
	FILE* fptr = fopen("bfs.out", "w");
	for (int i = 1; i < graph.numNodes + 1; i++)
		fprintf(fptr, "%d ", cost[i]);

	fclose(fptr);
}
int main()
{
	memset(cost, -1, 4 * size);
	int source;
	GraphVertex graph = readFile("bfs.in", &source);
	bfs(graph, source);
	print_out(graph);
	return 0;
}