[백준] P1260

import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

public class P1260 {
	static int[][] matrix;
	static boolean[] visit;
	static int v, e, s;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		v = sc.nextInt();
		e = sc.nextInt();
		s = sc.nextInt();
		matrix = new int[v + 1][v + 1];
		visit = new boolean[v + 1];
		int v1, v2;
		for (int i = 1; i <=e ; i++) {
			v1 = sc.nextInt();
			v2 = sc.nextInt();
			matrix[v1][v2] = matrix[v2][v1] = 1;
		}
		dfs(s);
		resetVisit();
		bfs(s);
		sc.close();
	}
	public static void resetVisit() {
		for (int i = 1; i < v + 1; i++) {
			visit[i] = false;
		}
		System.out.println();
	}
	public static void dfs(int s) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(s);
		int p;
		boolean flag;
		visit[s] = true;
		System.out.print(s + " ");
		while (!stack.isEmpty()) {
			p = stack.peek();
			flag = false;
			for (int i = 1; i < v + 1; i++) {
				if (matrix[p][i] == 1 & !visit[i]) {
					stack.push(i);
					visit[i] = true;
					System.out.print(i + " ");
					flag = true;
					break;
				}
			}
			if (!flag) {
				stack.pop();
			}
		}
	}
	public static void bfs(int s) {
		Queue<Integer> queue = new ArrayBlockingQueue<Integer>(v);
		queue.add(s);
		visit[s] = true;
		while (!queue.isEmpty()) {
			s = queue.poll();
			System.out.print(s + " ");
			for (int i = 1; i < v + 1; i++) {
				if (matrix[s][i] == 1 && !visit[i]) {
					queue.offer(i);
					visit[i] = true;
				}
			}
		}
	}
}