import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 정점 갯수
        int M = sc.nextInt(); // 간선 갯수
        int V = sc.nextInt(); // 탐색 시작 번호
        int[][] map = new int[N + 1][N + 1];

        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            map[a][b] = 1;
            map[b][a] = 1;
        }

        boolean[] dfsVisited = new boolean[N + 1];
        dfsVisited[V] = true;
        dfs(map, dfsVisited,  V);

        System.out.println();
        bfs(map, V);
    }

    private static void dfs(int[][] map, boolean[] visited, int currentNum) {
        System.out.print(currentNum + " ");

        for (int i = 1; i < map.length; i++) {
            if (map[currentNum][i] == 1 && !visited[i]) {
                visited[i] = true;
                dfs(map, visited, i);
            }
        }
    }

    private static void bfs(int[][] map, int startNum) {
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[map.length];

        queue.add(startNum);
        visited[startNum] = true;

        while (!queue.isEmpty()) {
            int currentNum = queue.poll();
            System.out.print(currentNum + " ");

            for (int i = 1; i < map.length; i++) {
                if (map[currentNum][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }

        System.out.println();
    }
}