You are given a connected undirected graph of ~n~ nodes and ~n~ or ~n-1~ edges (without parallel edges or self-loops). Starting from one node, in each step you may choose an edge connected with the current node and go to a node that is not visited previously, or move along the edge you passed through when you first visited the node and go back. When you are back to the start, you may choose to stop or continue, and you need to visit all vertices. If we write down the number of the vertex when we first visit a vertex, we shall end up with a sequence of length ~n~. Find the minimum possible sequence under the lexicographic order.
The input contains ~m+1~ lines. The first line contains space-separated integers ~n, m~ ~(m \le n)~.
In the following ~m~ lines, each line contains two integers ~u, v~ ~(1 \le u, v \le n)~ denoting there exists an edge between vertex ~u~ and vertex ~v~. The integers are separated by a space.
The output consists of one line with ~n~ integers denoting the lexicographically minimum sequence. Two adjacent integers are separated by one space.
Sample Input 1
6 5 1 3 2 3 2 5 3 4 4 6
Sample Output 1
1 3 2 5 4 6
Sample Input 2
6 6 1 3 2 3 2 5 3 4 4 5 4 6
Sample Output 2
1 3 2 4 5 6
Additional samples can be found here.
For all test cases, ~1 \le n \le 5\,000~, and ~m = n-1~ or ~m = n~.
|Test Case||~n=~||~m=~||Max degree|