시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB180522512312.106%

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

1 3 2 5 4

힌트

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

출처

  • 문제의 오타를 찾은 사람: cokcjswo
  • 데이터를 추가한 사람: topology
  • 문제를 만든 사람: xhark