$$$m$$$ 给你一个大小为 $$$n$$$ 的矩阵 $$$a$$$,其中包含从 $$$1$$$ 到 $$$n \cdot m$$$ 的整数排列。
$$$n$$$ 整数的排列是一个数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的所有数字恰好一次。例如,数组 $$$[1]$$$、$$$[2, 1, 3]$$$、$$$[5, 4, 3, 2, 1]$$$ 是排列,而数组 $$$[1, 1]$$$、$$$[100]$$$、$$$[1, 2, 4, 5]$$$ 不是排列。
如果当写出矩阵的所有元素时,所得数组是一个排列,则该矩阵包含一个排列。矩阵 $$$[[1, 2], [3, 4]]$$$, $$$[[1]]$$$, $$$[[1, 5, 3], [2, 6, 4]]$$$ 包含排列,而矩阵 $$$[[2]]$$$, $$$[[1, 1], [2, 2]]$$$, $$$[[1, 2], [100, 200]]$$$ 没有。
您可以在一次操作中执行以下两个操作之一:
- 选择列 $$$c$$$ 和 $$$d$$$ ($$$1 \le c, d \le m$$$, $$$c \ne d$$$) 并交换这些列;
- 选择行 $$$c$$$ 和 $$$d$$$ ($$$1 \le c, d \le n$$$, $$$c \ne d$$$) 并交换这些行。
您可以执行任意数量的操作。
给定原始矩阵 $$$a$$$ 和矩阵 $$$b$$$。您的任务是确定是否可以使用给定的操作将矩阵 $$$a$$$ 转换为矩阵 $$$b$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例描述的第一行包含 $$$2$$$ 整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le n \cdot m \le 2 \cdot 10^5$$$) — 矩阵的大小。
接下来的 $$$n$$$ 行包含 $$$m$$$ 个整数 $$$a_{ij}$$$ ($$$1 \le a_{ij} \le n \cdot m$$$)。保证矩阵 $$$a$$$ 是一个排列。
接下来的 $$$n$$$ 行包含 $$$m$$$ 个整数 $$$b_{ij}$$$ ($$$1 \le b_{ij} \le n \cdot m$$$)。保证矩阵 $$$b$$$ 是一个排列。
保证所有测试用例的值 $$$n \cdot m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果可以从第一个矩阵获得第二个矩阵,则输出“YES”,否则输出“NO”。
您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。
示例
输入 #1
7 1 1 1 1 2 2 1 2 3 4 4 3 2 1 2 2 1 2 3 4 4 3 1 2 3 4 1 5 9 6 12 10 4 8 7 11 3 2 1 5 9 6 12 10 4 8 7 11 3 2 3 3 1 5 9 6 4 2 3 8 7 9 5 1 2 4 6 7 8 3 2 3 1 2 6 5 4 3 6 1 2 3 4 5 1 5 5 1 2 3 4 4 2 5 1 3
输出 #1
YES YES NO YES YES NO YES
注意
在第二个示例中,原始矩阵如下所示:
$$$ \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} $$$
通过交换行 $$$1$$$ 和 $$$2$$$,它变成:
$$$ \begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix} $$$
通过交换列 $$$1$$$ 和 $$$2$$$,它变得等于矩阵 $$$b$$$:
$$$ \begin{pmatrix} 4 & 3 \\ 2 & 1 \end{pmatrix} $$$