P16756 [GKS 2020 #C] Stable Wall

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`。

在样例 #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 完成