你的老板派你去进行一次国际销售旅行。真是太棒了！

你有 $N$ 个城市（编号从 1 到 $N$）需要访问，可以通过一组城市间的双向航班到达。

所有城市都必须至少访问一次。为了做到这一点，你可以预订任意数量的机票，但需遵守以下条件：

• 每张机票包含 2 次航班，一次是从特定城市 $X$ 到另一个特定城市 $Y$（称为去程航班），另一次是从城市 $Y$ 到城市 $X$（称为回程航班）。
• 你必须在对应的回程航班之前使用去程航班（在此期间你可以使用其他航班）。
• 每个城市最多只能有 1 次去程航班，但对回程航班没有限制（多个回程航班可以到达同一个城市）。
• 你必须使用你所预订机票中的所有航班。
• 除此之外，你可以以任何你喜欢的顺序访问城市。
• 你可以从你选择的任何城市开始你的旅行。你不能乘坐去程航班前往你的起始城市。

现在，你本可以尝试最小化旅行的总距离，但你上次已经做过了，那样太无聊了。相反，你注意到每个城市都有一个独特的 5 位数邮政编码（ZIP code）。当你第一次访问一个城市时（包括你开始的城市），你会记下该城市的邮政编码，并将它们连接成一个大数字（按照你第一次访问每个城市的顺序连接）。你能得到的最小数字是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含两个整数：城市数量 $N$ 和可能的双向航班数量 $M$。

接下来 $N$ 行，第 $i$ 行包含第 $i$ 个城市的 5 位数邮政编码。邮政编码不会有前导零，且每个测试用例中的所有邮政编码都是唯一的。

接下来 $M$ 行，每行包含两个整数 $i$ 和 $j$ ($1 \le i < j \le N$)，表示第 $i$ 个城市和第 $j$ 个城市之间存在双向航班。每个测试用例中的所有航班都是唯一的。

保证你可以按照上述规则访问每一个城市。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是通过连接旅行中访问城市的邮政编码所能得到的最小数字。

数据范围

内存限制：1 GB。

$1 \le T \le 100$。

$0 \le M \le N * (N - 1) / 2$。

小数据集（15 分）

时间限制：10 秒。

$1 \le N \le 8$。

大数据集（30 分）

时间限制：20 秒。

$1 \le N \le 50$。

样例

样例输入 1

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

样例输出 1

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

说明

在最后一个样例测试用例中，为了获得最小数字，你应该执行以下操作序列：

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 的回程航班。