题目描述

题意：

John有很多朋友住在不同的街，想去拜访每位朋友，同时希望走的路最短。因为道路很窄，John在一条路上不能往回走。

John希望从家出发，拜访完所有的朋友之后回到自己的家，且总路程最短。John意识到如果可以每条路径都走一次，然后返回起点，应该是最短的路径。写一个程序帮助John找到这样的路径。

他保证对于任意一个路口来说，都有至少一个能走到任意一个街道的方法。

John意识到这样的路径可能不存在，所以如果对于一个图来说，所求路径不存在的话他希望你输出“Round trip does not exist.”（不含引号）

但John又意识到这样的路径也许不只有一个，如果出现了多条路径，他希望你告诉他所经过街道序列字典序最小的那一个解。

一个测试点有多个测试，具体格式可看样例：

输入格式：

每行有两个整数，x，y（1<=x<=m,1<=y<=m,x!=y）如果对应的测试点输入完毕，则x==0，y==0。如果两者不为0，则再输入一个整数num表示对应街道的编号（1<=num<=n）

最后以一个只有0 0的测试点为输入文件的结尾（该测试点不需要输出）

给出的每条街连接两个路口，最多有n条街道（编号从1到n），m个路口（编号从1到m）。

输出格式：

每一行对应一个测试点，若相应测试点有解，则依次输出所有解中街道编码序列字典序最小的那一个。若无解，则输出“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.

数据范围：

1<=n<=1995,1<=m<=44

来源：鸣谢Michael_Bryant(209 id:lifanding)上传题面