CF2093F Hackers and Neural Networks

黑客们再次尝试利用神经网络的输出来创造有趣的短语。这次，他们希望获得一个长度为 $n$ 的字符串数组 $a$。 最初，他们有一个长度为 $n$ 的数组 $c$，其中所有位置都是空白，用符号 $*$ 表示。例如，如果 $n=4$，那么初始时 $c=[*,*,*,*]$。 黑客们可以访问 $m$ 个神经网络，每个神经网络都有自己对请求的答案版本——一个长度为 $n$ 的字符串数组 $b_i$。 黑客们试图通过以下操作从数组 $c$ 得到数组 $a$： 1. 选择一个神经网络 $i$，它将执行对数组 $c$ 的下一个操作：随机选择一个空白位置（例如位置 $j$），并将 $c_j$ 替换为 $b_{i, j}$。例如，如果选择第一个神经网络且 $c = [*, \text{«like»}, *]$，而 $b_1 = [\text{«I»}, \text{«love»}, \text{«apples»}]$，那么经过第一个神经网络的操作后，$c$ 可能变为 $[\text{«I»}, \text{«like»}, *]$ 或 $[*, \text{«like»}, \text{«apples»}]$。 2. 选择一个位置 $j$，并将 $c_j$ 替换为空白。 不幸的是，由于黑客访问神经网络的方式，他们只能在所有操作完成后看到修改后的数组 $c$，因此他们必须提前指定完整的操作序列。 然而，神经网络的随机行为可能导致无法获得目标数组 $a$，或者需要过多的操作才能获得它。 因此，黑客们希望你能帮助他们选择一个操作序列，确保以最少的操作次数获得数组 $a$。 更正式地说，如果存在一个操作序列可以确保从数组 $c$ 得到数组 $a$，那么在所有这样的序列中，找出操作次数最少的序列，并输出其中的操作次数。 如果不存在将数组 $c$ 转换为数组 $a$ 的操作序列，则输出 $-1$。

第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 500$）——原始数组 $a$ 的长度和神经网络的数量。 每个测试用例的第二行包含数组 $a$，由 $n$ 个字符串 $a_i$（$1 \le |a_i| \le 10$）组成，用空格分隔。 接下来的 $m$ 行，每行包含一个数组 $b_i$，由 $n$ 个字符串 $b_{i, j}$（$1 \le |b_{i,j}| \le 10$）组成，用空格分隔。 保证所有测试用例的 $|a_i|$ 和 $|b_{i, j}|$ 的总和不超过 $2 \cdot 10^5$，且所有测试用例的 $n \cdot m$ 总和也不超过 $2 \cdot 10^5$。 保证输入字符串仅由大小写拉丁字母组成。 注意，每个输入字符串的长度不超过 $10$。

输出 $t$ 个数字——每个测试用例一个数字，每个数字单独占一行。 如果存在确保从第 $i$ 个测试用例的数组 $c$ 得到数组 $a$ 的操作序列，则第 $i$ 个数字是该序列的最小操作次数。 否则，对于第 $i$ 个数字，输出 $-1$。

翻译由 DeepSeek V3 完成