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

struct queue_node {
	int v;
	queue_node *next;
};

void enqueue(queue_node **frt, queue_node **bck, int value) {
	queue_node *back = *bck;

	if ( back == NULL ) {
		back = (queue_node*) malloc( sizeof(queue_node) );
		*frt = back;
	} else {
		back->next = (queue_node*) malloc( sizeof(queue_node) );
		back = back->next;
	}
	
	back->v = value;
	back->next = NULL;
	
	*bck = back;
}

int dequeue(queue_node **frt, queue_node **bck) {
	queue_node *front = *frt;

	if ( front == NULL ) {
		return -1;
	}

	queue_node *tmp = front;
	int value = front->v;
	front = front->next;
	free(tmp);
	
	*frt = front;
	if ( front == NULL ) {
		*bck = NULL;
	}
	
	return value;
}

int main() {

	int n, m, s;

	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	
	scanf("%d%d%d", &n, &m, &s);

	int *num_edges = (int*) calloc(n, sizeof(int)); // number of edges for every vertex
	int **matrix = (int**) malloc(n * sizeof(int*)); // adjacency matrix
	int *dist = (int*) malloc(n * sizeof(int)); // distance from s to each vertex
	
	fpos_t fpos = ftell(stdin);
	
	// finding the number of edges to each vertex
	int u, v;
	for (int i=0; i<m; i++) {
		scanf("%d%d", &u, &v);
		num_edges[u-1]++;
	}
	
	// allocating necessary memory for the adjacency matrix
	for (int i=0; i<n; i++) {
		matrix[i] = (int*) malloc( num_edges[i]*sizeof(int) );
	}

	fsetpos(stdin, &fpos);
	
	// filling the adjacency matrix
	int *tmp_num_edges = (int*) calloc(n, sizeof(int));
	for (int i=0; i<m; i++) {
		scanf("%d%d", &u, &v);
		matrix[u-1][ tmp_num_edges[u-1]++ ] = v-1;
	}
	free(tmp_num_edges);
	
	// initializing distance attributes
	for (int i=0; i<n; i++) {
		dist[i] = -1;
	}
	
	queue_node *front = NULL, *back = NULL;
	
	enqueue(&front, &back, s-1);
	dist[s-1] = 0;  // distance from s to s is 0

	// breadth first search
	int t; // temporary vertex
	while ( front != NULL ) {
		t = dequeue(&front, &back);
		for ( int i=0; i<num_edges[t]; i++ ) {
			if ( dist[ matrix[t][i] ] == -1 ) {
				dist[ matrix[t][i] ] = dist[t]+1;
				enqueue( &front, &back, matrix[t][i] );
			}
		}
	}

	for (int i=0; i<n; i++) {
		printf("%d ", dist[i]);
	}

}