//#include "./../utils.h"
//#include "./../queue/queue.h"

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

typedef enum error_code_s {
	OK 				= 0,
	OUT_OF_BOUNDS 	= 1,
	NULL_REF	 	= 2,
	INVALID_QUEUE	= 3,
	OUT_OF_MEM		= 4
} error_code_t;

#ifndef QUEUE_H
#define QUEUE_H

typedef struct qnode_s{
	struct qnode_s* next;
	void* data;	
} qnode_t;

typedef struct queue_s{
	qnode_t* head;
	qnode_t* tail;
	size_t count;
	size_t data_size;
} queue_t;


queue_t* 	 queue_create	(size_t data_size);
error_code_t queue_delete	(queue_t* queue);
queue_t*	 queue_copy		(queue_t* queue);
error_code_t queue_swap		(queue_t* queue_a, queue_t* queue_b);
error_code_t queue_empty	(queue_t* queue);

error_code_t queue_push		(queue_t* queue, void* data);
error_code_t queue_pop		(queue_t* queue);
const void*	 queue_front	(queue_t* queue);

size_t	     queue_count	(queue_t* queue);

#endif

// Functie privata
// creaza un nod nou pentru queue
// returneaza NULL daca datele de intrare sunt invalide 
// returneaza NULL daca nu ajunge memorie pentru alocarea nodului
// returneaza nodul nou daca alocarea a reusit
qnode_t* new_node(queue_t* queue, void* data){
	if(NULL == data || NULL == queue){
		return NULL;
	}

	qnode_t* node = malloc(sizeof(*node));
	if(NULL == node){
		return NULL;
	}

	node->data = malloc(queue->data_size);
	if(NULL == node->data){
		return NULL;
	}

	memcpy(node->data, data, queue->data_size);
	node->next = NULL;

	return node;
}

// Functie privata
// Elibereaza memoria alocata de un nod
// returneaza un error_code_t care descrie executia functiei
error_code_t free_node(qnode_t* node){
	if(NULL == node){
		return NULL_REF;
	}

	if(NULL == node->data){
		return INVALID_QUEUE;
	}

	free(node->data);
	free(node);
	node = NULL;

	return OK;
}

// Functie publica
// creaza un queue nou
// returneaza NULL daca data_size este 0
// returneaza NULL daca nu a ajuns memorie pentru alocare
// returneaza queue-ul daca alocarea a reusit
queue_t* queue_create(size_t data_size){
	if(0 == data_size){
		return NULL;
	}

	queue_t* queue = malloc(sizeof(*queue));
	if(NULL == queue){
		return NULL;
	}

	queue->head = NULL;
	queue->tail = NULL;
	queue->data_size = data_size;
	queue->count = 0;

	return queue;
}

// Functie publica
// sterge queue-ul din memorie
// returneaza un error_code_t care descrie executia functiei
error_code_t queue_delete(queue_t* queue){
	if(NULL == queue){
		return NULL_REF;
	}

	qnode_t* node = queue->head;
	while(NULL != node){
		qnode_t* next = node->next;

		error_code_t err = free_node(node);
		if(err != OK){
			return err;
		}

		node = next;
	}

	queue->head = queue->tail = NULL;

	free(queue);
	queue = NULL;
	return OK;
}

// Functie publica
// Creaza un queue nou, identic cu cel dat
// Returneaza NULL daca nu a ajuns memorie pentru copiere
// E posibil sa returneze NULL daca queue-ul e invalid
// Returneaza queue-ul copiat daca a reusit copierea
queue_t* queue_copy(queue_t* queue){
	if(NULL == queue){
		return NULL;
	}

	queue_t* copy = queue_create(queue->data_size);
	if(NULL == copy){
		return NULL;
	}

	qnode_t* node = queue->head;
	while(node != NULL){
		error_code_t err = queue_push(copy, node->data);
		if(err != OK){
			return NULL;
		}

		node = node->next;
	}

	return copy;
}

// Functie publica
// Schimba intre ele doua queue-uri
// returneaza un error_code_t care descrie executia functiei
error_code_t queue_swap(queue_t* queue_a, queue_t* queue_b){
	if(NULL == queue_a || NULL == queue_b){
		return NULL_REF;
	}

	qnode_t* head_a = queue_a->head;
	qnode_t* tail_a = queue_a->tail;
	size_t data_size_a = queue_a->data_size;
	size_t count_a = queue_a->count;

	queue_a->head = queue_b->head;
	queue_a->tail = queue_b->tail;
	queue_a->count = queue_b->count;
	queue_a->data_size = queue_b->data_size;

	queue_b->head = head_a;
	queue_b->tail = tail_a;
	queue_b->data_size = data_size_a;
	queue_b->count = count_a;

	return OK;
}

// Functie publica
// Sterge toate elementele din queue
// returneaza un error_code_t care descrie executia functiei
error_code_t queue_empty(queue_t* queue){
	if(NULL == queue){
		return NULL_REF;
	}

	qnode_t* node = queue->head;
	while(NULL != node){
		if(NULL != node->data){
			free(node->data);
		}else{
			return INVALID_QUEUE;
		}

		qnode_t* next = node->next;
		free(node);
		node = next;
	}

	queue->head = queue->tail = NULL;
	queue->count = 0;

	return OK;
}

// Functie publica
// Adauga un nou element la sfarsitul randului.
// returneaza un error_code_t care descrie executia functiei
error_code_t queue_push(queue_t* queue, void* data){
	if(NULL == data || NULL == queue){
		return NULL_REF;
	}

	if(NULL == queue->head){
		queue->head = new_node(queue, data);
		if(NULL == queue->head){
			return OUT_OF_MEM;
		}
		queue->tail = queue->head;
		queue->count = 1;

		return OK;
	}

	qnode_t* node = new_node(queue, data);
	if(NULL == node){
		return OUT_OF_MEM;
	}

	queue->tail->next = node;
	queue->tail = node;
	queue->count++;

	return OK;
}

// Functie publica
// Elimina primul element la rand
// returneaza un error_code_t care descrie executia functiei
error_code_t queue_pop(queue_t* queue){
	if(NULL == queue){
		return NULL_REF;
	}

	if(NULL == queue->head){
		return OK;
	}

	if(queue->head == queue->tail){
		error_code_t err = free_node(queue->head);
		if(err != OK){
			return err;
		}

		queue->count = 0;
		queue->head = queue->tail = NULL;
		return OK;
	}

	qnode_t* node = queue->head;
	queue->head = node->next;

	error_code_t err = free_node(node);
	if(err != OK){
		return err;
	}
	node = NULL;

	queue->count--;

	return OK;
}

// Functie publica
// Returneaza NULL daca queue-ul e invalid
// Returneaza valoarea primului element la rand
const void* queue_front(queue_t* queue){
	if(NULL == queue || NULL == queue->head || NULL == queue->head->data){
		return NULL;
	}

	return queue->head->data;
}

// Functie publica
// Returneaza numarul de elemente din queue 
// Returneaza 0 daca queue-ul dat este NULL
size_t queue_count(queue_t* queue){
	if(NULL == queue){
		return 0;
	}
	return queue->count;
}

queue_t* tree[100000];
int dist[100000];
char b[100000];

int min(int a, int b){
	return (a < b) * a + (a >= b) * b;
}


int main(){
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);

	int  N, M, S;
	scanf("%d %d %d", &N, &M, &S);
	for(int i = 0; i < N; i++){
		tree[i] = queue_create(sizeof(int));
		dist[i] = 1000001;
	}

	for(int i = 0; i < M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		x--;y--;
		queue_push(tree[x], &y);
	}

	S--;
	dist[S] = 0;

	queue_t* q = queue_create(sizeof(int));
	queue_push(q, &S);

	while(queue_count(q)){
		int top = *(int*)(queue_front(q));
		queue_pop(q);
		
		if(b[top]){
			continue;
		}

		while(queue_count(tree[top])){
			int child = *(int*)(queue_front(tree[top]));
			queue_pop(tree[top]);
			dist[child] = min(dist[child], dist[top] + 1);
			queue_push(q, &child);
		}

		b[top]  = 1;
	}

	for(int i = 0; i < N; i++){
		if(dist[i] >= 1000001)
			dist[i] = -1;
		printf("%d ", dist[i]);
	}

	return 0;
}