1084 . 一筆畫問題
TopCoder
Tags
Description
尤拉曾經證明在一個無向圖中，如果 每一個點的"度"（與這個點相接的邊的數目）都是偶數，或全部的點中只有兩個是有奇數的"度"，這個圖就有一條 一筆畫路徑。就是以一種走法走過所有的邊而每個邊最多只能走一次。
現在請寫一個程式再給定的圖 中找出一條一筆畫路徑，又一個圖中往往有超過一條一筆畫路徑，所以規定只有一條是符合要求的，這一條就是所有路徑中，字典順序最小的（例如 $\text{1 3 2 4}<\text{1 3 4 2}$）
Input Format
輸入檔可能包含多筆測試資料，每筆測試資料的第一列包含一個正整數 $M(1 \le M \le 1024)$，接下來 $M$ 列每列有兩個數 $i, j$，表示第 $k$ 條邊連接 $i$ 與 $j$ $(1 \le i, j \le 500)$。 其中任兩點間可能不止有一條邊相連。$M=0$ 代表輸入結束。
Output Format
對於每筆測試資料請輸出 $M+1$ 行加上一個空白行。每一行有一個正整數， 表示一條一筆畫路徑。可以假設輸入的圖一定有一條一筆畫路徑。
Sample Input 1
5
3 1
2 4
5 1
3 5
1 2
0
3 1
2 4
5 1
3 5
1 2
0
Sample Output 1
1
3
5
1
2
4
//這裡有個空白行
3
5
1
2
4
//這裡有個空白行
Hints
※對不起,測資弄太快了|||
Problem Source
原TIOJ1084 / 94建中校內資訊能力競賽(prob 2)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |