题目描述

Apollo 正在玩一个涉及多联骨牌的游戏。多联骨牌是由一个或多个正方形通过边相连构成的单一连通形状。游戏的目标是将 $N$ 个多联骨牌组合成一个没有洞的矩形。每个多联骨牌都标有一个从 A 到 Z 的唯一字符。

Apollo 已经完成了游戏，并创建了一个包含 $R$ 行和 $C$ 列的矩形墙壁。他拍了一张照片，并发送给他的朋友 Selene。Selene 喜欢墙壁的照片，但如果墙壁是稳定的，她会更喜欢。如果墙壁可以通过一次添加一个多联骨牌的方式构建，并且每个多联骨牌始终是被支撑的，则该墙壁是稳定的。一个多联骨牌是被支撑的，如果它的每个方格要么在地面上，要么下方有其他方格。

Apollo 想检查他的墙壁是否稳定，如果稳定，则通过告诉她添加多联骨牌的顺序来向 Selene 证明这一点。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $R$ 和 $C$。然后有 $R$ 行，从上到下描述墙壁。每行包含一个由 $C$ 个大写字母（A 到 Z）组成的字符串，描述该行的墙壁。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个由 $N$ 个大写字母组成的字符串，描述他构建多联骨牌的顺序。如果存在多个这样的顺序，输出任意一个。如果墙壁不稳定，则输出 -1。

4
4 6
ZOAAMM
ZOAOMM
ZOOOOM
ZZZZOM
4 4
XXOO
XFFO
XFXO
XXXO
5 3
XXX
XPX
XXX
XJX
XXX
3 10
AAABBCCDDE
AABBCCDDEE
AABBCCDDEE

Case #1: ZOAM
Case #2: -1
Case #3: -1
Case #4: EDCBA

提示

在样例 #1 中，注意 ZOMA 是另一个可能的答案。

在样例 #2 和样例 #3 中，墙壁不稳定，因此答案为 -1。

在样例 #4 中，唯一可能的答案是 EDCBA。

限制条件

$1 \le T \le 100$。

$1 \le R \le 30$。

$1 \le C \le 30$。

没有两个多联骨牌标有相同的字母。

输入保证符合题目描述中的规则。

测试集 1

$1 \le N \le 5$。

测试集 2

$1 \le N \le 26$。

翻译由 DeepSeek V4 Pro 完成