时间限制:1000 ms
内存限制:128 MiB
标准输入输出
题目类型:传统
评测方式:文本比较
约翰买了一辆新车,想要坐车去探望他的朋友们。
他的朋友数量很多,城镇上的每条街上都有他的朋友。
已知约翰所在的城镇,有 条街道(编号 到 ), 个路口(编号 到 ),每条街道都被两个路口连接,任意两条街道之间都是互通的。
城镇的街道和路口构成了一个无向连通图。
现在请你帮他找出一个旅行方案使得他从他的家所在的路口出发,经过所有的街道且每条街道只走一次,并且最终可以回到出发点。
输入包含多组测试用例。
每组测试用例包含若干行,每行包含三个整数,表示路口 和路口 之间有一条街道 。
假设每组测试用例中,第一行输入的路口 和 路口 中,数值较小的那个路口,即为约翰的家所在的路口。
当输入 时,表示该组测试用例结束输入。
当一组测试用例结束输入后,再次输入时,表示输入结束。
若存在方案,则按顺序输出方案中经过的街道的编号。
若存在多种方案,则输出字典序最小的那个。
若不存在方案,则输出 “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.