1629 . 快樂規劃路徑
TopCoder
Description
樹朋友們生活在一個湖邊，湖邊的樹依照順時針方向編號為1~n。
他們想要讓自己更快樂，所以發明了一種娛樂方式，就是找到一條路徑遍歷全部n棵樹剛好一遍。
要從A樹到B樹唯一的方法就是架一條很長的梯子直直伸過去。
可是當然不是任何兩棵樹都可以架梯子，所以他們會先把所有可能架梯子的樹對(沒有錯字!)給你。
當然，(A,B)表示A可以到B、B也可以到A。
但是給定的遊歷路徑不能出現任兩條梯子交叉，不然可能會讓想要快樂的樹朋友發生危險。
例如上圖粗線所示就是一個合法的快樂路徑。
給你樹的個數以及樹對，請輸出一組快樂路徑。
若有很多組解，樹朋友希望看到字典順序最小的那一組。
Input Format
第一行有一個樹字n，表示湖畔樹的數量。
第二行有一個樹字m，表示有多少樹對。
接下來有m行，每行有兩個樹字Ai, Bi。
表示Ai可以架梯子到Bi，Bi也可以架梯子到Ai。
一些限制：
5 <= n <= 1,000
1 <= Ai, Bi <= n
Output Format
輸出包含n行，每行有一個樹字Ki。
K1, K2, ... Kn就是一個字典順序最小的合法路徑。
若無解，只需輸出一行-1。
Sample Input 1
7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7
Sample Output 1
2
3
4
1
5
6
7
3
4
1
5
6
7
Hints
Problem Source
原TIOJ1629 / IOI '06 The Valley of Mexico
Problem Setter：ATP
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |