You are given a connected undirected graph of nodes and or 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 . Find the minimum possible sequence under the lexicographic order.
Input Specification
The input contains lines. The first line contains space-separated integers .
In the following lines, each line contains two integers denoting there exists an edge between vertex and vertex . The integers are separated by a space.
Output Specification
The output consists of one line with 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
Additional samples can be found here.
Constraints
For all test cases, , and or .
Test Case | Max degree | ||
---|---|---|---|
1-3 | N/A | ||
4-5 | |||
6-8 | |||
9-10 | N/A | ||
11-13 | |||
14-15 | N/A | ||
16-17 | |||
18-19 | |||
20-22 | |||
23-25 | N/A |
Comments