6609 - John’s trip

John有很多朋友住在不同的街,John想去拜访每位朋友,同时希望走的路最短。因为道路很窄,John在一条路上不能往回走。John希望从家里出发,拜访完所有的朋友后回到自己的家,且总的路程最短。John意识到如果可以每条道路只走一次然后返回起点应该是最短的路径,写一个程序帮助John找到这样的路径。给出每条街连接两个路口,最多由1995条街,最多44个路口,街编号由1到n,路口分别编号1到m。

输入

多组数据。

每组数据有多行,每行由三个整数组成:x,y,z。z为这条街的编号,x和y表示这条街连接的两个路口的编号。(实际数据中可能有自环)。

对于每组数据,John住在第一行中连接的两个顶点中编号较小的路口处。所有的街都可以连通到其他街上。“0 0”表示一组数据的结束,再一个“0 0”表示输入的结束。

输出

如果能找到所有街道遍历一次的回路,输出找到的路径。如果不存在,则输出“Round trip does not exist.”。

样例

输入

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

输出

1 2 3 4 5 6
Round trip does not exist.

来源

一本通

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题