package acm;

import java.util.*;
import java.io.*;

public class GraphTraversal {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String testCases = (br.readLine());
        //while (testCases!="") {
            int totalNodes;
            int totalEdges;
            String ne = br.readLine();
            totalNodes = Integer.parseInt(ne.split(" ")[0]);
            totalEdges = Integer.parseInt(ne.split(" ")[1]);
            LinkedList<LinkedList> graphInfo = new LinkedList<LinkedList>();
            for(int i=0;i<totalNodes;i++){
                LinkedList al=new LinkedList();
                graphInfo.add(i,al);
            }
            int edge = 1;
            String aPlusB = br.readLine();
            int root=Integer.parseInt(aPlusB.split(" ")[0]);
            while (edge <= totalEdges) {
                int A = Integer.parseInt(aPlusB.split(" ")[0]);
                int B = Integer.parseInt(aPlusB.split(" ")[1]);
                processGraphInfo(graphInfo, A, B);
                aPlusB = br.readLine();
                edge++;
            }

            for (int i = 0; i < graphInfo.size(); i++) {
                LinkedList al = graphInfo.get(i);
                Collections.sort(al);
            }
            System.out.println(testCases);
            //Breadth First;
            Queue q=new LinkedList();
            q.add((Integer)root);
            for(int i=0;i<graphInfo.size();i++){
                LinkedList ll=(LinkedList)graphInfo.get(i);
                for(int j=0;j<ll.size();j++){
                    Integer num=(Integer)ll.get(j);
                    if(q.contains(num)){
                        continue;
                    }else{
                        q.add(num);
                    }
                }
            }
            int i=1;
            int queueSize=q.size();
            while(!q.isEmpty()){
                if(i==queueSize){
                    System.out.print(q.poll());
                }else{
                    System.out.print(q.poll()+", ");
                }
                i++;
            }
            System.out.println("");
            //Depth First
            Stack stk=new Stack();
            int j=0;
            while(true){
                for(int i1=0;i1<graphInfo.size();i1++){
                    LinkedList ll=(LinkedList)graphInfo.get(i1);
                    for(int i2=j;i2<ll.size();i2++){
                        Integer num=(Integer)ll.get(i2);
                        if(root!=num && !stk.contains(num)){
                            stk.add(num);
                            break;
                        }else{
                            continue;
                        }
                    }
                }
                if(stk.size()!=(totalNodes-1)){
                    j++;
                }else if(stk.size()==(totalNodes-1)){
                    stk.add(root);
                    break;
                }
            }

            while(!q.isEmpty()){
                if(i==queueSize){
                    System.out.print(q.poll());
                }else{
                    System.out.print(q.poll()+", ");
                }
                i++;
            }
            while(!stk.isEmpty()){
                if(stk.size()==1){
                    System.out.print(stk.pop());
                }else{
                    System.out.print(stk.pop()+", ");
                }

            }
        //  testCases = (br.readLine());
        //}
    }

    // Adjacency List
    public static void processGraphInfo(LinkedList ll, int a, int b) {
        LinkedList tmpA=(LinkedList)ll.get(a);
        LinkedList tmpB=(LinkedList)ll.get(b);
        tmpA.add(b);
        tmpB.add(a);
    }
}