#3705. 「一本通 3.7 练习 3」John's Trip 暂未评定

时间限制:1000 ms 内存限制:64 MiB 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: root

注意

出题人配置了 Special Judge 程序。本题答案可能不唯一或者题目有特殊要求,请注意审题。

题目描述

来自 CERC 1995

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

输入格式

多组数据。
每组数据有多行,每行由三个整数组成: 为这条街的编号, 表示这条街连接的两个路口的编号。可能有自环。
对于每组数据,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 5 4 6
Round trip does not exist.

数据范围与提示

最多有 条街,最多 个路口。