그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search)이 있습니다.

DFS는 한 방향으로 갈 수 있는 데까지 깊이 탐색해가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법입니다.

반면 BFS는 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

정점의 개수 N, 간선의 개수 M, 그리고 탐색을 시작할 정점의 번호 V가 주어졌을 때, DFS로 탐색한 결과와 BFS로 탐색한 결과를 각각 출력하는 프로그램을 작성하시오.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 합니다. 더 이상 방문할 수 있는 정점이 없는 경우 탐색을 종료합니다.

입력

첫째 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 공백을 사이에 두고 주어진다.

둘째 줄부터 M개의 줄에 걸쳐 각 간선의 양 끝점 u와 v가 공백을 사이에 두고 주어진다. 간선은 양방향(무방향)이며, 동일한 간선이 중복되어 주어지지 않는다.

출력

첫째 줄에는 DFS를 수행한 결과를, 둘째 줄에는 BFS를 수행한 결과를 출력한다. 각 줄에는 시작 정점 V부터 방문한 정점을 순서대로 공백으로 구분하여 출력해야 한다.

제한 사항

• 1 ≤ N, M ≤ 1,000
• 1 ≤ V ≤ N
• 1 ≤ u, v ≤ N (단, u ≠ v 이며, 자기 자신으로 향하는 간선은 없다.)
• 입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있습니다.

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4