문제
동현이는 방이 N개인 미로의 지도를 갖고 있다.
각 방에는 1번부터 N번까지 번호가 매겨져 있고, N개의 방 사이에는 M개의 문이 있으며,
각 문은 서로 다른 두 방을 연결한다.
동현이는 1번 방에서 출발해서 N개의 방을 모두 탐색해 볼 것이다.
동현이는 모험심이 강하기 때문에 항상 새로운 방을 찾기를 원한다.
동현이는 자신이 위치한 방과 연결된 방 중 한 번도 들르지 않은 방이 있다면 그 중 가장 번호가 작은 방으로 가고,
그렇지 않으면(연결된 방이 모두 전에 들렀던 방이면) 그냥 왔던 곳으로 되돌아가게 된다.
동현이가 N개의 방을 모두 방문하고 1번 방으로 오면 동현이는 탐색을 끝낸다.
N개의 방을, 동현이가 먼저 방문한 순으로 정렬하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 방의 수 N과 문의 수 M이 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000)
두 번째 줄부터 M개의 줄에는 각 문이 연결하는 두 방의 번호가 입력된다.
모든 방들은 문을 통해 연결되어 있고, 임의의 두 방 사이에는 최대 1개의 문이 있다.
전체 데이터의 38%는 2 ≤ N ≤ 3,000 이다.
출력
첫 번째 줄에 동현이가 방문한 순서대로 N개의 방의 번호를 정렬하여 출력한다.
예제1
입력
56
13
34
42
21
14
45
출력
12435
힌트
출처
@functionx