#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000000
typedef struct node {
	int name;
	int cost;
	int numNeighbours;
	int* neighbours;
}node;

int N, M, start;

int stack[MAX];
int indexStack;

/*void push(struct node x) {
	stack[indexStack++] = x;
}

struct node pop() {
	if (indexStack > 0) {
		node value = stack[0];
		for (int i = 1; i < indexStack; i++)
			stack[i - 1] = stack[i];
		indexStack--;
		return value;
	}
}*/

node* readFile(const char* filename) {
	FILE* f = fopen(filename, "r");
	node* nodes=NULL;
	fscanf(f, "%d %d %d", &N, &M, &start);

	nodes = (node*)malloc(N * sizeof(node));
	
	for (int i = 1; i <= N; i++) {
		nodes[i].name = i;
		nodes[i].cost = -1;
		nodes[i].numNeighbours = 0;
		nodes[i].neighbours = NULL;
	}

	int x, y;

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

	fclose(f);
	return nodes;
}


void BFS(node* graph, int s) {
	graph[s].cost = 0;
	int L = 1;    
	stack[L] = s;  //push cu primul nod
	for(int i=1;i<=L;i++){     //parcurg vecinii nodului pe care il scot
		for (int j = 0; j < graph[stack[i]].numNeighbours; j++) {    
			if (graph[graph[stack[i]].neighbours[j]].cost == -1) {  //daca e nevizitat crest costul cu 1
				stack[++L] = graph[stack[i]].neighbours[j];
				graph[stack[L]].cost = graph[stack[i]].cost+1;
			}
		}
	}
}

int main() {

	node* list = readFile("bfs.in");

	FILE* f = fopen("bfs.out", "w");
	BFS(list, start);

	for (int i = 1; i <= N; i++)
		fprintf(f,"%d ", list[i].cost);

	fclose(f);
	return 0;
}