TopCoder

User's AC Ratio

90.9% (30/33)

Submission's AC Ratio

33.5% (53/158)

Description

尤拉曾經證明在一個無向圖中,如果 每一個點的"度"(與這個點相接的邊的數目)都是偶數,或全部的點中只有兩個是有奇數的"度",這個圖就有一條 一筆畫路徑。就是以一種走法走過所有的邊而每個邊最多只能走一次。

現在請寫一個程式再給定的圖 中找出一條一筆畫路徑,又一個圖中往往有超過一條一筆畫路徑,所以規定只有一條是符合要求的,這一條就是所有路徑中,字典順序最小的(例如1 3 2 4 < 1 3 4 2)

Input Format

輸入檔可能包含多筆測試資料,每筆測試資料的第一列包含一個正整數M (1 <= M <= 1024),接下來M列每列有兩個數i, j,表示第k條邊連接i與j(1 <= i, j <= 500)。 其中任兩點間可能不止有一條邊相連。M=0代表輸入結束。

Output Format

對於每筆測試資料請輸出 M+1 行加上一個空白行。每一行有一個正整數, 表示一條一筆畫路徑。可以假設輸入的圖一定有一條一筆畫路徑。

Sample Input

5
3 1
2 4
5 1
3 5
1 2
0

Sample Output

1
3
5
1
2
4
//這裡有個空白行

Hints

※對不起,測資弄太快了|||

Problem Source

原TIOJ1084 / 94建中校內資訊能力競賽(prob 2)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 65536