$N$개의 정점과 $M$개의 간선으로 이루어진 무향 그래프 $G$가 주어진다. $G$에 대해 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 수행한 결과를 출력하자. $G$는 다음을 만족한다.

• 정점 $u, v$를 잇는 간선이 있을 때, $u$와 $v$가 같은 경우는 존재하지 않는다.
• 어느 두 정점을 골라도 두 정점을 잇는 경로는 반드시 존재한다.
• 두 정점을 직접적으로 잇는 간선은 최대 한 개 이하이다.

DFS와 BFS를 수행함에 있어서 아래의 규칙을 따라야 한다.

• 처음 탐색을 시작하는 정점은 $1$번 정점이다.
• 임의의 정점에서 다음으로 방문할 수 있는 정점이 여러 개라면, 번호가 작은 정점부터 탐색한다.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. $(1 ≤ N ≤ 1,000; 1 ≤ M ≤ 10,000)$

둘째 줄부터 $M$개의 줄에 걸쳐 $M_i$번째 간선이 잇는 두 정점 $u, v$가 공백으로 구분되어 주어진다. $(1 ≤ u, v ≤ N)$

첫째 줄에 DFS에서 $1, 2, ... , N$번째로 방문되는 정점을 공백으로 구분하여 출력한다.

둘째 줄에 BFS에서 $1, 2, ... , N$번째로 방문되는 정점을 공백으로 구분하여 출력한다.