Problems
Donghyun has provided a map of the maze with N rooms. Each room is numbered from 1 to N, and there are M doors between the N rooms. Each door connects two different rooms.
Donghyun is planning to explore all the rooms in the maze. Donghyun will start at the room numbered 1.
Since Donghyun is adventurous, he prefers exploring new rooms rather than revisiting old ones. When he encounters multiple unvisited connected rooms, he goes to the one with the smallest number. If all connected rooms have already been visited, he returns to the room he came from.
Donghyun finishes the exploration after visiting all rooms and returning to room 1.
Write a program that sorts N rooms by the order of Donghyun’s first visit.
Input
The first line contains the number of rooms N and the number of doors M (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000).
Following M lines contain the numbers of the two rooms connected by each door.
All rooms are connected by doors, and there is at most one door between any two rooms.
38% of the total data satisfy 2 ≤ N ≤ 3,000.
Output
In the first line, print the numbers of N rooms in the order in which Donghyun visited them.
Example
5 6
1 3
3 4
4 2
2 1
1 4
4 5
1 2 4 3 5
The map of the maze is as follows:
At this time, Donghyun explores the maze in the order 1→2→4→3→4→5→4→2→1.
You must sign in to write code.