민식 우선 탐색

민식 우선 탐색은 깊이 우선 탐색과 같은 방식으로 진행되는 그래프 탐색이다.

현재 정점에서 방문할 수 있는 정점은 현재 정점과 간선으로 연결되어 있고 아직 방문하지 않은 정점이다. 다음 정점은 이 후보 정점들의 번호를 오름차순으로 보았을 때 다음 규칙으로 정한다.

• 후보가 홀수 개이면 가운데 번호의 정점을 방문한다.
• 후보가 짝수 개이면 가장 작은 번호의 정점을 방문한다.

선택한 정점으로 이동해 같은 규칙을 재귀적으로 수행하고, 더 이상 갈 수 있는 정점이 없으면 직전 정점으로 돌아간다.

1번 정점에서 탐색을 시작할 때, 정점을 처음 방문하는 순서를 출력하라.

첫째 줄에 정점의 개수 N(N <= 100,000)과 간선의 개수 M(M <= 1,000,000)이 주어진다.

다음 M개의 줄에는 두 정수 a, b가 주어지며, 이는 정점 a와 정점 b가 간선으로 연결되어 있음을 의미한다. 모든 간선은 양방향이다. 정점 번호는 1부터 N까지이다.

1번 정점에서 시작한 민식 우선 탐색에서 정점을 처음 방문한 순서를 공백으로 구분해 출력한다.

제공된 테스트의 그래프에서는 1 -> 3 -> 2 -> 5 -> 2 -> 3 -> 4 순서로 이동하므로 처음 방문한 정점의 순서는 1 3 2 5 4이다.