1376번 - 민식우선탐색

문제

DFS와 BFS는 아는가? DFS는 깊이우선탐색, BFS는 넓이우선탐색이다.

이번에는 mFS! 그래, 듣도 보도 못했던 듣보잡 탐색방법인, 민식우선탐색이다.

민식이는 DFS를 할 줄 모르기 때문에 다음과 이 탐색방법을 만들어냈다.

이 탐색방법을 설명하자면 다음과 같다.

기본틀은 DFS와 완전히 동일하다. 그런데 한가지 다른 점이 있다면, 한 점에서 다른 정점을 방문할 때 순서가 다르다. 현재 점에서 방문할 수 있는 정점(갈 수 있으면서 방문한 적 없는 정점들)들이 홀수개면 그 정점 번호들의 중간값인 정점으로 방문을 시작하고, 짝수개면 가장 작은 정점 번호로 방문을 시작한다.

당신의 임무는, 1번 정점에서 출발하여 민식우선탐색을 하는 순서를 찍는 것이다.

입력

첫째 줄에는 정점의 개수 N(<=100,000)과 간선의 개수 M(<=1,000,000)이 주어진다. 두 번째 줄부터 M+1번째 줄 까지는 a b의 형태로 a와 b가 간선으로 연결되어 있다는 의미의 입력이 들어온다. 모든 간선은 양방향이다.

출력

민식우선탐색의 순서를 출력한다.

제한

힌트

1->3->2->5->2->3->4의 순서로 움직인다.