문제

$N$개의 정점과 $M$개의 무향 간선으로 이루어진 그래프가 주어진다. 각 정점에는 $1$부터 $N$까지 번호가 매겨져 있다.

이 그래프에서 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 수행했을 때의 정점 방문 순서를 출력해 보자. 단, 탐색 시작 정점은 $1$번 정점이고 방문 가능한 정점이 여러 개라면 정점 번호가 작은 정점을 먼저 방문한다.

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($2\le N\le 100\,000;\ 1\le M\le 300\,000$)

둘째 줄부터 $M$개의 줄에 걸쳐 각 줄에 각 간선이 연결하는 두 정점 $u$, $v$가 공백으로 구분되어 주어진다. ($1\le u, v\le N;\ u\neq v$)

두 정점을 연결하는 간선이 여러 개 주어질 수도 있음에 유의하자.

출력

첫째 줄에 깊이 우선 탐색의 정점 방문 순서를 출력한다.

둘째 줄에 너비 우선 탐색의 정점 방문 순서를 출력한다.

예제 입력 1

7 8
1 2
2 3
4 2
3 6
6 7
1 4
7 1
4 5

예제 출력 1

1 2 3 6 7 4 5
1 2 4 7 3 5 6

예제 입력 2

10 1
1 2

예제 출력 2

1 2
1 2