← 返回题目列表

Codeforces · 2093/F

F. 黑客和神经网络

中文机器翻译题面 查看原题

黑客再次尝试使用神经网络的输出创建有趣的短语。这次,他们想要获得长度为 $$$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{《喜欢》}、*]$$$ 或 $$$[*、\text{《喜欢》}、\text{《苹果》}]$$$。

  2. 选择位置 $$$j$$$ 并将 $$$c_j$$$ 替换为空格。

不幸的是,由于黑客访问神经网络的方式,他们只有在所有操作完成后才能看到修改后的数组$$$c$$$,因此他们必须提前指定整个操作顺序。

然而,神经网络的随机行为可能会导致永远无法获得所需数组的情况,或者获得它需要过多的操作次数。

因此,黑客指望您帮助选择操作顺序,以保证以最少的操作次数获取数组$$$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$$$ 个测试用例中获取数组 $$$a$$$ 的操作序列,则第 $$$i$$$ 个数字是该序列中最小的操作数。

否则,对于第$$$i$$$个数字,输出$$$-1$$$。

示例

输入
复制

4
3 3
I love apples
He likes apples
I love cats
They love dogs
3 2
Icy wake up
wake Icy up
wake up Icy
4 3
c o D E
c o D s
c O l S
c o m E
4 5
a s k A
d s D t
O R i A
a X b Y
b a k A
u s k J

输出
复制

5
-1
6
8