// BFS.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define maxn 100005
#define oo  1 << 30

typedef struct my_list {
	int node;
	struct my_list *next;
} list;

void add_edge(list **head, int val) {
	if (((*head) == NULL)) {
		(*head) = (list*)malloc(sizeof(list));
		(*head)->node = val;
		(*head)->next = NULL;
	} else {
		list *new_node = (list*)malloc(sizeof(list));
		new_node->node = val;
		new_node->next = (*head);
		(*head) = new_node;
	}
}

void push(list **first, list **last, int val) {
	if ((*first) == NULL) {
		(*first) = (list*)malloc(sizeof(list));
		(*first)->node = val;
		(*first)->next = NULL;
		(*last) = (*first);
	}	else {
		list *new_node = (list*)malloc(sizeof(list));
		new_node->node = val;
		new_node->next = NULL;
		(*last) = new_node;
	}
}

void pop(list **first) {
	(*first) = (*first)->next;
}

void Bfs(list *G[maxn], int start, int Dist[]) {
	list *first = NULL, *last = NULL, *it;
	Dist[start] = 0;
	push(&first, &last, start);
	while (first != NULL) {
		int node = first->node;
		pop(&first);
		for (it = G[node]; it != NULL; it = it->next) {
			if (Dist[it->node] > Dist[node] + 1) {
				Dist[it->node] = Dist[node] + 1;
				push(&first, &last, it->node);
			}
		}
	}
}

int main() {
	FILE *fin = fopen("bfs.in", "r");
	FILE *fout = fopen("bfs.out", "w");
	list *G[maxn];
	int n, m, x, y, i, start, Dist[maxn];
	fscanf(fin, "%d %d %d", &n, &m, &start);
	for (i = 0; i <= n; i++) {
		G[i] = NULL;
		Dist[i] = oo;
	}
	for (i = 0; i < m; i++) {
		fscanf(fin, "%d %d", &x, &y);
		add_edge(&G[x], y);
	}
	Bfs(G, start, Dist);
	for (i = 1; i <= n; i++) {
		if (Dist[i] == oo) Dist[i] = -1;
		fprintf(fout, "%d ", Dist[i]);
	}
	fprintf(fout, "\n");
	fclose(fin);
	fclose(fout);
    return 0;
}