描述

小约翰尼得到了一辆新车。他决定开车在镇上转转，去拜访他的朋友。约翰尼想要拜访他所有的朋友，但他的朋友有很多。在镇上的每条街道他都有一个朋友。他开始思考如何让他的行程尽可能短。很快他意识到，最好的办法是每条街道只走一次。自然地，他希望在他的父母家（也就是他的出发地）结束他的行程。

约翰尼所在镇上的街道用从 1 到 \(n\) 的整数命名，\(n < 1995\)。路口独立地用从 1 到 \(m\) 的整数命名，\(m \leq 44\)。没有一个路口连接超过 44 条街道。镇上的每个路口都有不同的编号。每条街道恰好连接两个路口。镇上没有两条街道有相同的编号。他立刻开始规划他的环形行程。如果有多个这样的环形行程，他会选择按街道编号序列字典序最小的那个。但约翰尼甚至找不到一个这样的环形行程。

帮助约翰尼并编写一个程序来找到所需的最短环形行程。如果不存在这样的环形行程，程序应该输出一条消息。假设约翰尼住在输入中出现的第一条街道所连接的编号较小的那个路口。镇上的所有街道都是双向的。从镇上的每条街道都可以到达其他街道。镇上的街道非常狭窄，一旦约翰尼进入街道就不可能掉头。

输入

输入文件由几个数据块组成。每个数据块描述一个城镇。数据块中的每一行包含三个整数 \(x\)、\(y\)、\(z\)，其中 \(x > 0\) 且 \(y > 0\) 是由编号为 \(z\) 的街道连接的两个路口的编号。当一行中 \(x = y = 0\) 时表示一个数据块的结束。在输入文件的末尾有一个空的数据块，即 \(x = y = 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.

来源

1995 年中欧