← 返回题目列表

Codeforces · 1980/E

E. 行和列的排列

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

$$$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} $$$