P13252 [GCJ 2014 #1B] The Bored Traveling Salesman

你的老板派你出差去进行国际销售。多么令人激动的事情啊！ 你需要拜访 $N$ 座城市（编号从 $1$ 到 $N$），这些城市之间有若干双向航班可供选择。 你必须至少访问每座城市一次。为此，你可以预订任意数量的机票，但需要满足以下规则： - 每张机票包含两段航班：一段是从某个特定城市 $X$ 飞往另一个特定城市 $Y$（称为**去程航班**），另一段是从城市 $Y$ 返回城市 $X$（称为**返程航班**）。 - 你必须先使用某张机票的去程航班，之后才能使用其返程航班（中间可以穿插其他航班）。 - 每个城市最多只能作为去程航班的目的地一次，但返程航班的目的地没有限制（同一城市可以接收多个返程航班）。 - 所有你购买的机票中的航班必须全部使用。 - 除此之外，你可以按任意顺序访问城市。 - 你可以从任意一座城市开始旅程。但注意，不能乘坐任何一张机票的去程航班抵达起始城市。 这一次你不再尝试最小化旅行总距离，那太无聊了。相反，你注意到每座城市都有一个独特的 $5$ 位数邮政编码（ZIP code）。你会在**首次访问某座城市**时（包括起始城市）将其 ZIP code 记录下来，并按访问顺序将这些 ZIP code 串接成一个大数字。 你的目标是：通过选择航线和访问顺序，使这个最终拼接出的数字尽可能小。

输入的第一行为测试用例数 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含两个整数：城市数 $N$ 和可用的双向航班数 $M$。 接下来的 $N$ 行，第 $i$ 行是第 $i$ 个城市的 $5$ 位邮政编码。所有 ZIP code 在每个测试用例中均不重复，且不会有前导零。 接下来 $M$ 行，每行包含两个整数 $i$ 和 $j$（$1 \leq i < j \leq N$），表示存在一条从城市 $i$ 到城市 $j$ 的双向航班。每个测试用例中的所有航班均不重复。 保证在遵守规则的前提下，你可以访问到所有城市。

对于每个测试用例，输出一行 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你能通过合理选择航线与访问顺序拼接出的最小数字。

**样例说明** 以最后一个测试用例为例，以下是使最终拼接数字最小的一种访问顺序与航线选择方式： 1. 从城市 $1$ 出发，记录 $10001$。 2. 乘坐从 $1$ 到 $2$ 的去程航班，记录 $10002$。 3. 乘坐从 $2$ 到 $3$ 的去程航班，记录 $10003$。 4. 乘坐从 $3$ 返回 $2$ 的返程航班。 5. 乘坐从 $2$ 到 $4$ 的去程航班，记录 $10004$。 6. 乘坐从 $4$ 到 $5$ 的去程航班，记录 $10005$。 7. 乘坐从 $5$ 返回 $4$ 的返程航班。 8. 乘坐从 $4$ 返回 $2$ 的返程航班。 9. 乘坐从 $2$ 返回 $1$ 的返程航班。 10. 乘坐从 $1$ 到 $6$ 的去程航班，记录 $10006$。 11. 乘坐从 $6$ 返回 $1$ 的返程航班。 ## 限制条件 - $1 \leq T \leq 100$ - $0\le M\le \frac{N\times(N-1)}{2}$ ### Small 数据集（15 分） - 时间限制：~~60~~ 3 秒 - $1 \leq N \leq 8$ ### Large 数据集（30 分） - 时间限制：~~120~~ 5 秒 - $1 \leq N \leq 50$ 翻译由 ChatGPT-4o 完成。