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

int ct = 1;

typedef struct graf {

    int node;
    struct graf* next;

} grafT;

grafT** array;

typedef struct bfs {

    int node;
    struct bfs* next;

} bfsT;

bfsT* first,* last;

void initialize(int n) {

    for(int i = 0; i <= n; i++) {

        array[i] = NULL;

    }

}

void init() {

    first = last = NULL;

}

grafT* findLast(grafT** current) {


    grafT* el = *current;
    while(el->next != NULL)
        el = el->next;

    return el;

}

void add(grafT** current, int node) {

    if(*current == NULL) {

        (*current) = (grafT*)malloc(sizeof(grafT));
        (*current)->node = node;
        (*current)->next = NULL;

    } else {

        grafT* element = (grafT*)malloc(sizeof(grafT));
        element->next = *current;
        element->node = node;
        *current = element;

    }
}


void addLast(int node) {

    if(first == NULL) {
        first = (bfsT*)malloc(sizeof(bfsT));
        first->node = node;
        first->next = last;
        last = first;

    } else {

        bfsT* current = (bfsT*)malloc(sizeof(bfsT));
        current->node = node;
        last->next = current;
        current->next = NULL;
        last = current;

    }
}

void deleteFirst() {


    if(first->next == NULL) {

        free(first);
        init();

    }

    if(first == NULL) {

        return;

    }

    bfsT* current = first;
    first = first->next;
    free(current);

}

void bfs(int* visited, int s) {

    addLast(s);
    while(first != NULL) {
        printf("%d\n", first->node);
        int node = first->node;
        deleteFirst();
        grafT* current = array[node];

        while(current != NULL) {
            printf("%d\n", current->node);
            if(visited[current->node] == -1) {

                visited[current->node] = ct;
                addLast(current->node);

            }
            current = current->next;
        }

        ct++;

    }
}

void read(int m, FILE* in) {

    int node1, node2;

    for(int i = 0; i < m; i++) {

        fscanf(in, "%d %d", &node1, &node2);
        add(&array[node1], node2);

    }

}

int main() {

    FILE* in = fopen("bfs.in", "r");
    FILE* out = fopen("bfs.out", "w");

    int n, m, s;

    fscanf(in, "%d %d %d", &n, &m, &s);
    array = (grafT**)malloc(sizeof(grafT*) * (n + 1));
    initialize(n);
    init();

    read(m, in);


    int* visited = (int*)malloc(sizeof(int) * (n + 1));

    for(int i = 0; i <= n; i++)
        visited[i] = -1;

    visited[s] = ct - 1;

    bfs(visited, s);

    for(int i = 1; i <= n; i++)
        fprintf(out, "%d ", visited[i]);
    return 0;
}