黑客再次尝试使用神经网络的输出创建有趣的短语。这次,他们想要获得长度为 $$$n$$$ 的字符串数组 $$$a$$$。
最初,它们有一个长度为 $$$n$$$ 的数组 $$$c$$$,用空格填充,用符号 $$$*$$$ 表示。因此,如果 $$$n=4$$$,则最初 $$$c=[*,*,*,*]$$$。
黑客可以访问 $$$m$$$ 神经网络,每个神经网络都有自己的请求答案版本 - 长度为 $$$n$$$ 的字符串数组 $$$b_i$$$。
黑客试图使用以下操作从数组 $$$c$$$ 中获取数组 $$$a$$$:
- 选择一个神经网络 $$$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{《苹果》}]$$$。
- 选择位置 $$$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