#10003. [CF2093F] 黑客与神经网络

卡评测将会被封号。

黑客们再次尝试利用神经网络的输出来创造有趣的短语。这次，他们希望获得一个长度为 的字符串数组 。

最初，他们有一个长度为 的数组 ，其中所有位置都是空白，用符号 表示。例如，如果 ，那么初始时 。

黑客们可以访问 个神经网络，每个神经网络都有自己对请求的答案版本——一个长度为 的字符串数组 。

黑客们试图通过以下操作从数组 得到数组 ：

1. 选择一个神经网络 ，它将执行对数组 的下一个操作：随机选择一个空白位置（例如位置 ），并将 替换为 。例如，如果选择第一个神经网络且 ，而 ，那么经过第一个神经网络的操作后， 可能变为 或 。
2. 选择一个位置 ，并将 替换为空白。

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

然而，神经网络的随机行为可能导致无法获得目标数组 ，或者需要过多的操作才能获得它。

因此，黑客们希望你能帮助他们选择一个操作序列，确保以最少的操作次数获得数组 。

更正式地说，如果存在一个操作序列可以确保从数组 得到数组 ，那么在所有这样的序列中，找出操作次数最少的序列，并输出其中的操作次数。

如果不存在将数组 转换为数组 的操作序列，则输出 。

第一行包含一个整数 （）——测试用例的数量。

每个测试用例的第一行包含两个整数 和 （）——原始数组 的长度和神经网络的数量。

每个测试用例的第二行包含数组 ，由 个字符串 （）组成，用空格分隔。

接下来的 行，每行包含一个数组 ，由 个字符串 （）组成，用空格分隔。

保证所有测试用例的 和 的总和不超过 ，且所有测试用例的 总和也不超过 。

保证输入字符串仅由大小写拉丁字母组成。

注意，每个输入字符串的长度不超过 。

输出 个数字——每个测试用例一个数字，每个数字单独占一行。

如果存在确保从第 个测试用例的数组 得到数组 的操作序列，则第 个数字是该序列的最小操作次数。

否则，对于第 个数字，输出 。

输入 #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

输出 #1

5
-1
6
8