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

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

#define nMax 100001

int viz[nMax], coada[nMax];

struct node
{
	int val;
	node *next;
};

void insertFront(node * &hd, int v)
{
	printf("no\n");
	node *elem = (node*)malloc(sizeof(struct node));
	elem->val = v;
	elem->next = hd;
	hd = elem;
}

int main()
{
	FILE *in, *out;
	fopen_s(&in, "bfs.in", "r");
	fopen_s(&out, "bfs.out", "w");

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

	node *head[nMax] = { NULL };

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

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

	while (st <= dr) {
		int currentNode = coada[st++];
		node *nod = head[currentNode];
		while (nod != NULL) {
			if (viz[nod->val] == -1) {
				coada[++dr] = nod->val;
				viz[nod->val] = viz[currentNode] + 1;
			}
			nod = nod->next;
		}
	}

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