Minsik-First Search

Minsik-first search is a graph traversal that follows the same backtracking structure as depth-first search.

At the current vertex, the available vertices are adjacent vertices that have not been visited yet. Sort their numbers in increasing order, then choose the next vertex by the following rule.

• If there is an odd number of available vertices, visit the middle-numbered vertex.
• If there is an even number of available vertices, visit the smallest-numbered vertex.

After moving to the chosen vertex, apply the same rule recursively. If the current vertex has no available vertex left, return to the previous vertex.

Starting from vertex 1, output the order in which vertices are first visited.

The first line contains the number of vertices N (N <= 100,000) and the number of edges M (M <= 1,000,000).

Each of the next M lines contains two integers a and b, meaning that vertex a and vertex b are connected by an edge. All edges are undirected. Vertices are numbered from 1 to N.

Output the order in which vertices are first visited by Minsik-first search starting from vertex 1, separated by spaces.

For the provided test graph, the traversal moves 1 -> 3 -> 2 -> 5 -> 2 -> 3 -> 4, so the first-visit order is 1 3 2 5 4.