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

#define nMax 100001

int viz[nMax], coada[nMax];

typedef struct node {
	int data;
	struct node* next;
} node;

FILE *in, *out;

node* create(int data, node* next)
{
	node* newNode = (node*)malloc(sizeof(node));
	if (newNode == NULL) {
		printf("Error when creating a new node\n");
		return NULL;
	}
	newNode->data = data;
	newNode->next = next;
	return newNode;
}

node* insertFront(int data, node* head)
{
	node* newNode = create(data, head);
	head = newNode;
	return head;
}

int main()
{
	node* head[nMax] = { NULL };

	fopen_s(&in, "bfs.in", "r");
	fopen_s(&out, "bfs.out", "w");

	int n, m, S, a, b;
	fscanf_s(in, "%d%d%d", &n, &m, &S);

	for (int i = 1; i <= m; i++) {
		fscanf_s(in, "%d%d", &a, &b);
		head[a] = insertFront(b, head[a]);
	}

	for (int i = 1; i <= n; i++) {
		viz[i] = -1;
	}
	viz[S] = 0;
	int st = 1, dr = 0;
	coada[++dr] = S;

	while (st <= dr) {
		int curr = coada[st++];
		node* cursor = head[curr];
		while (cursor != NULL) {
			int nxt = cursor->data;
			if (viz[nxt] == -1) {
				viz[nxt] = viz[curr] + 1;
				coada[++dr] = nxt;
			}
			cursor = cursor->next;
		}
	}

	for (int i = 1; i <= n; i++) {
		fprintf(out, "%d ", viz[i]);
	}

}