Description

你的老板派你出差去进行国际销售。多么令人激动的事情啊！

你需要拜访 $N$ 座城市（编号从 $1$ 到 $N$），这些城市之间有若干双向航班可供选择。

你必须至少访问每座城市一次。为此，你可以预订任意数量的机票，但需要满足以下规则：

• 每张机票包含两段航班：一段是从某个特定城市 $X$ 飞往另一个特定城市 $Y$（称为去程航班），另一段是从城市 $Y$ 返回城市 $X$（称为返程航班）。
• 你必须先使用某张机票的去程航班，之后才能使用其返程航班（中间可以穿插其他航班）。
• 每个城市最多只能作为去程航班的目的地一次，但返程航班的目的地没有限制（同一城市可以接收多个返程航班）。
• 所有你购买的机票中的航班必须全部使用。
• 除此之外，你可以按任意顺序访问城市。
• 你可以从任意一座城市开始旅程。但注意，不能乘坐任何一张机票的去程航班抵达起始城市。

这一次你不再尝试最小化旅行总距离，那太无聊了。相反，你注意到每座城市都有一个独特的 $5$ 位数邮政编码（ZIP code）。你会在首次访问某座城市时（包括起始城市）将其 ZIP code 记录下来，并按访问顺序将这些 ZIP code 串接成一个大数字。

你的目标是：通过选择航线和访问顺序，使这个最终拼接出的数字尽可能小。

Input Format

输入的第一行为测试用例数 $T$。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个整数：城市数 $N$ 和可用的双向航班数 $M$。

接下来的 $N$ 行，第 $i$ 行是第 $i$ 个城市的 $5$ 位邮政编码。所有 ZIP code 在每个测试用例中均不重复，且不会有前导零。

接下来 $M$ 行，每行包含两个整数 $i$ 和 $j$（$1 \leq i < j \leq N$），表示存在一条从城市 $i$ 到城市 $j$ 的双向航班。每个测试用例中的所有航班均不重复。

保证在遵守规则的前提下，你可以访问到所有城市。

Output Format

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

4
3 2
10001
20000
10000
1 2
2 3
5 4
36642
28444
50012
29651
10953
1 4
2 3
2 5
4 5
5 5
36642
28444
50012
29651
10953
1 2
1 4
2 3
2 5
4 5
6 6
10001
10002
10003
10004
10005
10006
1 2
1 6
2 3
2 4
3 5
4 5

Case #1: 100002000010001
Case #2: 1095328444500122965136642
Case #3: 1095328444366422965150012
Case #4: 100011000210003100041000510006

Hint

样例说明

以最后一个测试用例为例，以下是使最终拼接数字最小的一种访问顺序与航线选择方式：

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 完成。