1531：John‘s Trip

题目描述

来自 CERC 1995

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

输入格式

多组数据。

每组数据有多行，每行由三个整数组成：$x, y, z$。$z$ 为这条街的编号，$x$ 和 $y$ 表示这条街连接的两个路口的编号。可能有自环。

对于每组数据，John 住在第一行中连接的两个顶点中编号较小的路口处。所有的街都可以连通到其他街上。$0$ 表示一组数据的结束。

再一个 $0$ 表示输入的结束。

输出格式

如果能找到所有街道遍历一次的回路，输出找到的路径，两个整数之间用一个空格隔开，行末无空格。如果不存在，输出 "Round trip does not exist."。

样例

样例输入 #1

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

1 2 3 5 4 6
Round trip does not exist.

样例解释 #1

第一组数据：

• 路口编号 $1..m$（$m=3$），街道编号 $1..n$（$n=6$）。
• 街道：
  1. 连接路口 $1$ 和 $2$，编号 $1$
  2. 连接路口 $2$ 和 $3$，编号 $2$
  3. 连接路口 $3$ 和 $1$，编号 $6$
  4. 连接路口 $1$ 和 $2$，编号 $5$（重边）
  5. 连接路口 $2$ 和 $3$，编号 $3$
  6. 连接路口 $3$ 和 $1$，编号 $4$
• John 住在第一行连接的两个顶点中编号较小的路口，即路口 $1$。
• 要求从路口 $1$ 出发，经过每条街道恰好一次，最后回到路口 $1$（即欧拉回路）。
• 存在这样的回路，输出街道编号序列：1 2 3 5 4 6（注意是街道编号，不是路口编号）。
• 验证：按这个序列走街道，可以从 $1$ 出发并回到 $1$。

第二组数据：

• 路口 $1..4$，街道 $1..4$：
  1. 连接 $1$ 和 $2$，编号 $1$
  2. 连接 $2$ 和 $3$，编号 $2$
  3. 连接 $1$ 和 $3$，编号 $3$
  4. 连接 $2$ 和 $4$，编号 $4$
• John 住在路口 $1$（第一行中较小的路口）。
• 该图不存在欧拉回路（因为路口 $2$ 的度数为 $3$，奇数；路口 $4$ 的度数为 $1$，奇数；奇数度顶点个数不为 $0$）。
• 输出 Round trip does not exist.。

数据范围

• 最多有 $1995$ 条街（边）
• 最多有 $44$ 个路口（顶点）

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题要求从指定起点（第一行中编号较小的路口）出发，找一条欧拉回路，输出边的编号序列。图是无向的，可能有重边和自环。首先判断是否存在欧拉回路：所有顶点的度数均为偶数，且所有边属于同一个连通分量（忽略孤立点）。然后使用 Hierholzer 算法求欧拉回路，注意需要按街道编号顺序输出（题目要求输出街道编号序列，且字典序最小？样例输出似乎是按字典序最小输出街道编号序列）。在算法中，当有多个可选边时，选择街道编号最小的边。由于顶点数 $\le 44$，边数 $\le 1995$，可以用邻接矩阵或邻接表存储，并排序边。注意输入格式：每组数据以 0 0 结束，整个输入以单独一行 0 结束（即再一个 0）。需要处理多组数据。