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

#define INF 2140000000
#define MaxN 100005

typedef struct _Node {
    struct _Node *next;
    int data;
} Node;

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

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

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

    return list;
}

static inline Node *make_node(int new_data) {
    Node *new_node = (Node *) malloc(sizeof(Node));
    new_node->data = new_data;

    return new_node;
}

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

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

static inline int list_front(LinkedList *list) {
    return list->head->data;
}

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

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

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

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

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

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

int main() {
    int n, m, s, v[MaxN] = {}, start, final;
    LinkedList *q = list_init();
    int *Graph[MaxN], size[MaxN] = {}, max_size[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] = (int *)malloc(sizeof(int));
        max_size[i] = 1;
        v[i] = INF;
    }
    v[s] = 0;


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

    while(!list_is_empty(q)) {
        int node = list_front(q);
        list_pop_front(q);
        for(int i = 0; i < size[node]; i++)
            if(v[Graph[node][i]] > v[node] + 1) {
                list_push_back(q, Graph[node][i]);
                v[Graph[node][i]] = 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;
}