#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;

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

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

    return list;
}

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

    return new_node;
}

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

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

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

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);
}

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++;
}

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);
    for(int i = 1; i <= m; i++) {
        fscanf(IN, "%d%d", &start, &final);
        list_push_back(Graph[start], final);
    }

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