Lexicographically Smallest Travel Itinerary

Little Y is an OI enthusiast who loves traveling. In country X, there are n cities connected by m bidirectional roads. Each road connects two distinct cities, and no two roads connect the same pair of cities. Furthermore, the road network is connected, which means that from any city, one can reach any other city using these roads.

Little Y can start her journey from an arbitrarily chosen city. Starting from the chosen city, at each step she may travel along a road to an as-yet unvisited city or backtrack along the road she took when she first visited a city. Whenever she arrives at a city for the first time (including the starting city), she records the city’s number. Once she returns to the starting city, she may either end her journey or continue traveling.

It is guaranteed that her travel plan will visit every city at least once, thereby forming a sequence of exactly n numbers. Little Y wants this recorded sequence to be lexicographically smallest. For two sequences A and B of length n, we say that A is lexicographically smaller than B if there exists a positive integer x such that:

• A_i = B_i for every 1 ≤ i < x, and
• A_x < B_x.

Your task is to help Little Y determine the lexicographically smallest sequence possible.

Note: It is optimal to start at the smallest numbered city to achieve a lexicographically smallest sequence. Then, using a greedy strategy, always choose the smallest available adjacent city (from those that are reachable from the already visited set) until all cities have been visited.

Input Format in terms of Graph:

• There are n cities and m bidirectional roads.
• Road configuration ensures that the graph is simple and connected.

inputFormat

The first line contains two integers n and m representing the number of cities and roads respectively.

The following m lines each contain two integers u and v, indicating that there is a bidirectional road connecting city u and city v.

You can assume that there are no duplicate roads and no road connects a city with itself. Also, the road network is connected.

outputFormat

Print the lexicographically smallest sequence of n integers (separated by spaces) representing the order in which the cities are visited for the first time.

sample

4 4
1 2
1 3
2 4
3 4

1 2 3 4