D · 使两方格相等的最少操作次数

题目描述

时间限制：2000ms 内存限制：512MB 给你两个方格 $A$ 和 $B$，每个方格有 $H$ 行和 $W$ 列。 对于满足 $1 \leq i \leq H$ 和 $1 \leq j \leq W$ 的每一对整数 $(i, j)$，令 $(i, j)$ 表示 $i$ 行和 $j$ 列中的单元格。在方格 $A$ 中，单元格 $(i, j)$ 包含整数 $A_{i, j}$。在方格 $B$ 中，单元格 $(i, j)$ 包含整数 $B_{i, j}$。 你可以执行任意次以下操作，也可以不做任何操作。在每次操作中，从以下两种方式中选择一种： - 选择一个整数 $i(1 \leq i \leq H-1)$，然后交换方格 $A$ 中的 $i$ 行和 $(i+1)$ 行。 - 选择一个整数 $i(1 \leq i \leq W-1)$，然后交换方格 $A$ 中的 $i$ 列和 $(i+1)$ 列。 判断是否可以通过重复上述操作使方格 $A$ 与方格 $B$ 相同。如果可以则输出所需的最少操作次数。 注意：当且仅当对于满足 $1 \leq i \leq H$ 和 $1 \leq j \leq W$ 的所有整数对 $(i, j)$ 来说，在方格 $A$ 的单元格 $(i, j)$ 中的整数等于在方格 $B$ 的单元格 $(i, j)$ 中的整数时，方格 $A$ 才与方格 $B$ 相同。

每个测试点包含多个测试用例。第一行为测试用例的总数 $t(1 \le t \le 5)$。 每个测试用例的第一行为两个矩阵的行数 $H(2 \le H \le 5)$ 和列数 $W(2 \le W \le 5)$。 每个测试用例的第 $2$ 行到 $H + 1$ 行，每行包含 $W$ 个整数 $A_{i, j}(1 \le A_{i, j} \le 10^9)$ 表示方格 $A$ 中的数字。 每个测试用例的第 $H+2$ 行到 $H \times 2 + 1$ 行，每行包含 $W$ 个整数 $B_{i, j}(1 \le B_{i, j} \le 10^9)$ 表示方格 $B$ 中的数字。 对于每个测试用例具体的输入内容参考以下格式： $H$ $W$ $A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$ $\vdots$ $A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$ $B_{1, 1}$ $B_{1, 2}$ $\cdots$ $B_{1, W}$ $B_{2, 1}$ $B_{2, 2}$ $\cdots$ $B_{2, W}$ $\vdots$ $B_{H, 1}$ $B_{H, 2}$ $\cdots$ $B_{H, W}$

对于每个测试用例的如果无法使方格 $A$ 与方格 $B$ 相同，则输出 $-1$。否则，输出使方格 $A$ 与方格 $B$ 相同所需的最少操作次数。

输入 #1

2
4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
1 3 2 5 4
11 13 12 15 14
6 8 7 10 9
16 18 17 20 19
2 2
1 1
1 1
1 1
1 1000000000

输出 #1

3
-1