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

using namespace std;

// 전역 변수: 최대 정점 1000개, 간선은 여유 있게 설정
vector<int> adj[1001]; 
bool visited[1001];    

// 방문 배열을 초기화하는 함수 (DFS와 BFS 실행 사이에 호출)
void resetVisited() {
    for (int i = 0; i < 1001; i = i + 1) {
        visited[i] = false;
    }
}

// DFS: 재귀를 이용한 탐색
void dfs(int current) {
    visited[current] = true; // 현재 위치 방문 도장 쾅!
    cout << current << " ";

    for (int i = 0; i < adj[current].size(); i = i + 1) {
        int next = adj[current][i];
        // 연결된 곳 중 아직 안 가본 곳이 있다면
        if (visited[next] == false) {
            dfs(next); // 그 방향으로 더 깊이 들어감
        }
    }
}

// BFS: for 문과 vector를 이용한 탐색
void bfs(int start) {
    vector<int> q; 
    q.push_back(start); // 시작점 넣기
    visited[start] = true;

    // head가 q.size()보다 작은 동안 계속 반복
    // q.push_back이 실행될 때마다 q.size()가 늘어나서 for문이 계속 돌아갑니다.
    for (int head = 0; head < q.size(); head = head + 1) {
        int curr = q[head]; // 현재 순서의 노드를 꺼냄
        cout << curr << " ";

        for (int i = 0; i < adj[curr].size(); i = i + 1) {
            int next = adj[curr][i];
            // 연결된 곳 중 아직 안 가본 곳이 있다면
            if (visited[next] == false) {
                visited[next] = true; // 방문 도장 쾅!
                q.push_back(next);    // 다음에 가볼 곳으로 저장
            }
        }
    }
}

int main() {
    int n, m, v;
    cin >> n >> m >> v;

    // 1. 그래프 데이터 입력받기
    for (int i = 0; i < m; i = i + 1) {
        int s, e;
        cin >> s >> e;
        adj[s].push_back(e);
        adj[e].push_back(s); // 양방향 연결
    }

    // 2. 작은 번호부터 방문하기 위해 정렬 (필수 조건)
    for (int i = 1; i <= n; i = i + 1) {
        sort(adj[i].begin(), adj[i].end());
    }

    // 3. DFS 실행
    resetVisited();
    dfs(v);
    cout << endl; // 줄바꿈

    // 4. BFS 실행
    resetVisited();
    bfs(v);
    cout << endl; // 줄바꿈

    return 0;
}