import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Main{

  static Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
  static LinkedHashSet<Integer> dfsVisited = new LinkedHashSet<>();
  static LinkedHashSet<Integer> bfsVisited = new LinkedHashSet<>();

  public static void dfs(int start) {
    dfsVisited.add(start);
    if (graph.get(start) != null) {
      for (int neighbor : graph.get(start)) {
        if (!dfsVisited.contains(neighbor)) {
          dfs(neighbor);
        }
      }
    }
  }

  public static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    bfsVisited.add(start);

    while (!queue.isEmpty()) {
      Integer poll = queue.poll();
      if (graph.get(poll) != null) {
        for (int neighbor : graph.get(poll)) {
          if (!bfsVisited.contains(neighbor)) {
            queue.add(neighbor);
            bfsVisited.add(neighbor);
          }
        }
      }
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // Vertex Edge Start
    int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    for (int i = 0; i < split[1]; i++) {
      int[] edge = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
      graph.putIfAbsent(edge[0], new ArrayList<>());
      graph.putIfAbsent(edge[1], new ArrayList<>());
      graph.get(edge[0]).add(edge[1]);
      graph.get(edge[1]).add(edge[0]); // 양방향
    }

    for (ArrayList<Integer> neighbor : graph.values()) {
      Collections.sort(neighbor);
    }

    dfs(split[2]);
    StringBuilder sb = new StringBuilder();
    for (int i : dfsVisited) {
      sb.append(i).append(" ");
    }
    System.out.println(sb.substring(0, sb.length() - 1));

    bfs(split[2]);
    StringBuilder sb2 = new StringBuilder();
    for (int i : bfsVisited) {
      sb2.append(i).append(" ");
    }
    System.out.println(sb2.substring(0, sb2.length() - 1));

  }
}