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

#define INF 2140000000
#define MaxN 100005

typedef struct _Node {
    struct _Node *next, *prev;
    void *data;
    size_t data_size;
} Node;

typedef struct _LinkedList {
    Node *head, *tail;
    size_t size;
}LinkedList;

LinkedList *list_init() {
    LinkedList *list = (LinkedList *) malloc(sizeof(LinkedList));

    list->head = list->tail = NULL;
    list->size = 0;

    return list;
}

Node *make_node(void *new_data, size_t data_size) {
    Node *new_node = (Node *) malloc(sizeof(Node));

    new_node->data = malloc(data_size);
    new_node->data_size = data_size;
    memcpy(new_node->data, new_data, data_size);

    return new_node;
}

size_t list_get_size(LinkedList *list) {
    return list->size;
}

int list_is_empty(LinkedList *list) {
    return list->size == 0;
}

Node *list_front(LinkedList *list) {
    return list->head;
}

Node *list_back(LinkedList *list) {
    return list->tail;
}

void list_push_front(LinkedList *list, void *new_data, size_t data_size) {
    Node *new_node = make_node(new_data, data_size);
    
    new_node->next = list->head;
    new_node->prev = NULL;
    if(list->size == 0)
        list->tail = new_node;
    else
        list->head->prev = new_node;
    list->head=new_node;
    
    list->size++;
}

void list_pop_front(LinkedList *list) {
    Node *node = list->head;

    if(list->size == 1)
        list->tail = NULL;
    list->head = list->head->next;
    if(list->head != NULL)
        list->head->prev = NULL;

    list->size--;
    free(node->data);
    free(node);
}

void list_push_back(LinkedList *list, void *new_data, size_t data_size) {
    Node *new_node = make_node(new_data, data_size);
    
    new_node->next = NULL;
    new_node->prev = list->tail;
    if(list->size == 0)
        list->head = new_node;
    else
        list->tail->next = new_node;
    list->tail = new_node;
    
    list->size++;
}

void list_pop_back(LinkedList *list) {
    Node *node = list->tail;

    if(list->size == 1)
        list->head = NULL;
    list->tail = list->tail->prev;
    if(list->tail != NULL)
        list->tail->next = NULL;

    list->size--;
    free(node->data);
    free(node);
}

void list_clear(LinkedList *list) {
    while(list->size > 0)
        list_pop_front(list);
}

void list_free(LinkedList *list) {
    list_clear(list);
    free(list);
}

int main() {
    int n, m, s, v[MaxN] = {}, start, final;
    LinkedList *q = list_init(), *Graph[MaxN];    
    FILE *IN = fopen("bfs.in", "r");
    FILE *OUT = fopen("bfs.out", "w");

    fscanf(IN, "%d%d%d", &n, &m, &s);
    
    for(int i = 1; i <= n; i++) {
        Graph[i] = list_init();
        v[i] = INF;
    }
    v[s] = 0;


    list_push_back(q, &s, sizeof(int));
    for(int i = 1; i <= m; i++) {
        fscanf(IN, "%d%d", &start, &final);
        list_push_back(Graph[start], &final, sizeof(int));
    }

    while(!list_is_empty(q)) {
        int node = *(int *)list_front(q)->data;
        list_pop_front(q);
        for(Node *it = Graph[node]->head; it != NULL; it = it->next)
            if(v[*(int *)it->data] > v[node] + 1) {
                list_push_back(q, (int *)it->data, sizeof(int));
                v[*(int *)it->data] = v[node] + 1;
            }    
    }

    for(int i = 1; i <= n; i++) {
        if(v[i] == INF)
            fprintf(OUT, "-1 ");
        else
            fprintf(OUT, "%d ", v[i]);
    }

    list_free(q);    

    for(int i = 1; i <= n; i++) {
        list_free(Graph[i]);
    }

    fclose(IN);
    fclose(OUT);

    return 0;
}