P15137 [SWERC 2025] Chamber of Secrets 2

你正在玩游戏哈利·波特与密室 $2$。你想解锁下一关，即密室。入口门上有 $n$ 个面板，每个面板显示一个由 $m$ 个符号组成的序列。乘积 $nm$ 是偶数。系统通过以下四步过程从一个**秘密排列**生成这些序列： - 首先，从一个秘密排列 $[p_1, p_2, \dots, p_{nm/2}]$ 开始； - 然后，通过将秘密排列与自身连接来重复它，形成数组 $[b_1, b_2, \dots, b_{nm}]$； - 接着，将这个数组分割成 $n$ 个连续的块，即长度为 $m$ 的不相交子数组； - 最后，将这些块以任意顺序打乱并分配到各个面板上。 你被给出了系统产生的最终 $n$ 个面板序列。第 $i$ 个面板显示 $[a_{i,1}, a_{i,2}, \dots, a_{i,m}]$。你的任务是恢复一个可能的原始秘密排列 $[p_1, p_2, \dots, p_{nm/2}]$。对于给定的输入，至少存在一个解。如果有多个秘密排列有效，输出其中任意一个。 两个数组 $[x_1, x_2, \dots, x_{k_1}]$ 和 $[y_1, y_2, \dots, y_{k_2}]$ 的连接是长度为 $k_1 + k_2$ 的数组 $[x_1, x_2, \dots, x_{k_1}, y_1, y_2, \dots, y_{k_2}]$。 长度为 $l$ 的一个排列是一个由 $1$ 到 $l$ 的 $l$ 个不同整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现两次），并且 $[1,3,4]$ 也不是排列（$l = 3$ 但数组中有 $4$）。

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。接下来是对于每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n, m$（$1 \le n \le 70$, $1 \le m \le 70$）—— 面板的数量和每个显示序列的长度。 接下来的 $n$ 行中的第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$（$1 \le a_{i,j} \le nm/2$），表示第 $i$ 个面板上显示的序列。 注意，所有测试用例中的 $n$ 和 $m$ 之和没有约束。

对于每个测试用例，输出一行，包含一个秘密排列 $[p_1, p_2, \dots, p_{nm/2}]$，使得上述过程可以产生 $n$ 个面板序列 $[a_{i,1}, a_{i,2}, \dots, a_{i,m}]$。对于给定的输入，保证至少存在一个解。

#### 样例解释 在第一个测试用例中，一个有效的秘密排列是 $[p_1, p_2, \dots, p_{nm/2}] = [5, 6, 3, 4, 1, 2]$： - 数组 $[b_1, b_2, \dots, b_{nm}]$ 是 $[p_1, p_2, \dots, p_{nm/2}] = [5, 6, 3, 4, 1, 2]$ 的两个副本的连接； - $[b_1, b_2, \dots, b_{nm}]$ 分割成块 $[5, 6]$, $[3, 4]$, $[1, 2]$, $[5, 6]$, $[3, 4]$, $[1, 2]$； - 打乱后，最终的面板序列 $[a_{i,1}, a_{i,2}, \dots, a_{i,m}]$ 可以与这些块一致。 翻译由 DeepSeek 完成