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.
一本通