#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, V;

vector<int> graph[1001];
bool visited[1001];


// DFS
void dfs(int v) {

    visited[v] = true;
    cout << v << " ";

    for (int i = 0; i < graph[v].size(); i++) {

        int next = graph[v][i];

        if (!visited[next]) {
            dfs(next);
        }
    }
}


// BFS (for문 사용)
void bfs(int start) {

    vector<int> q;

    visited[start] = true;
    q.push_back(start);

   
    for (int i = 0; i < q.size(); i++) {

        int now = q[i];

        cout << now << " ";

        for (int j = 0; j < graph[now].size(); j++) {

            int next = graph[now][j];

            if (!visited[next]) {

                visited[next] = true;
                q.push_back(next);
            }
        }
    }
}


int main() {

    cin >> N >> M >> V;

    // 간선 입력
    for (int i = 0; i < M; i++) {

        int a, b;
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // 정렬
    for (int i = 1; i <= N; i++) {

        sort(graph[i].begin(), graph[i].end());
    }

    // DFS
    dfs(V);

    cout << "\n";

    // visited 초기화
    for (int i = 1; i <= N; i++) {

        visited[i] = false;
    }

    // BFS
    bfs(V);

    return 0;
}