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

typedef struct node {

	int key;
	struct node* next;

}node;

typedef enum { WHITE, GRAY, BLACK } color;

node* adj[100001];
int d[100001];
color c[1000001];

void enqueue(node** first, int key) {

	node* x = (node *)malloc(sizeof(node));
	if (x == NULL) {

		perror("malloc failed");
		exit(1);
	}

	x->key = key;
	x->next = NULL;

	if (*first == NULL) {

		*first = x;
	}
	else {

		node* p = *first;

		while (p->next != NULL) {

			p = p->next;
		}

		p->next = x;
	}
}

int dequeue(node** first) {

	if (*first == NULL) {

		return -1;
	}

	node* p = *first;
	int key = p->key;

	*first = p->next;
	p->next = NULL;

	return key;
}

void BFS(int s) {

	node* q = NULL;
	c[s] = GRAY;
	d[s] = 0;

	enqueue(&q, s);

	while (q != NULL) {

		int n = dequeue(&q);
		node* p = adj[n];

		while (p) {

			if (c[p->key] == WHITE) {

				enqueue(&q, p->key);
				d[p->key] = d[n] + 1;
				c[p->key] = GRAY;
			}

			p = p->next;
		}

		c[n] = BLACK;
	}
}

int main() {

	FILE* ip;
	FILE* op;

	ip = fopen("bfs.in", "r");
	if (ip == NULL) {

		perror("Error opening input file");
		return 1;
	}

	op = fopen("bfs.out", "w");
	if (op == NULL) {

		perror("Error opening output file");
		return 1;
	}

	int n, m, s;

	fscanf(ip, "%d", &n);
	fscanf(ip, "%d", &m);
	fscanf(ip, "%d", &s);

	for (int i = 0; i < m; i++) {

		int x, y;

		fscanf(ip, "%d", &x);
		fscanf(ip, "%d", &y);

		enqueue(&adj[x], y);
	}

	for (int i = 1; i <= n; i++) {

		d[i] = -1;
	}

	BFS(s);

	for (int i = 1; i <= n; i++) {

		fprintf(op, "%d ", d[i]);
	}

	fclose(ip);
	fclose(op);

	return 0;
}