311394: CF1980E. Permutation of Rows and Columns

E. Permutation of Rows and Columnstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have been given a matrix $a$ of size $n$ by $m$, containing a permutation of integers from $1$ to $n \cdot m$.

A permutation of $n$ integers is an array containing all numbers from $1$ to $n$ exactly once. For example, the arrays $[1]$, $[2, 1, 3]$, $[5, 4, 3, 2, 1]$ are permutations, while the arrays $[1, 1]$, $[100]$, $[1, 2, 4, 5]$ are not.

A matrix contains a permutation if, when all its elements are written out, the resulting array is a permutation. Matrices $[[1, 2], [3, 4]]$, $[[1]]$, $[[1, 5, 3], [2, 6, 4]]$ contain permutations, while matrices $[[2]]$, $[[1, 1], [2, 2]]$, $[[1, 2], [100, 200]]$ do not.

You can perform one of the following two actions in one operation:

• choose columns $c$ and $d$ ($1 \le c, d \le m$, $c \ne d$) and swap these columns;
• choose rows $c$ and $d$ ($1 \le c, d \le n$, $c \ne d$) and swap these rows.

You can perform any number of operations.

You are given the original matrix $a$ and the matrix $b$. Your task is to determine whether it is possible to transform matrix $a$ into matrix $b$ using the given operations.

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case description contains $2$ integers $n$ and $m$ ($1 \le n, m \le n \cdot m \le 2 \cdot 10^5$) — the sizes of the matrix.

The next $n$ lines contain $m$ integers $a_{ij}$ each ($1 \le a_{ij} \le n \cdot m$). It is guaranteed that matrix $a$ is a permutation.

The next $n$ lines contain $m$ integers $b_{ij}$ each ($1 \le b_{ij} \le n \cdot m$). It is guaranteed that matrix $b$ is a permutation.

It is guaranteed that the sum of the values $n \cdot m$ for all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output "YES" if the second matrix can be obtained from the first, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

ExampleInput

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

Output

YES
YES
NO
YES
YES
NO
YES

Note

In the second example, the original matrix looks like this:

$ \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} $

By swapping rows $1$ and $2$, it becomes:

$ \begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix} $

By swapping columns $1$ and $2$, it becomes equal to matrix $b$:

$ \begin{pmatrix} 4 & 3 \\ 2 & 1 \end{pmatrix} $

题目大意：
给定一个n行m列的矩阵a，包含1到n*m的整数排列。可以通过以下两种操作将矩阵a转换为矩阵b：
1. 选择两列c和d（1≤c,d≤m，c≠d）并交换它们；
2. 选择两行c和d（1≤c,d≤n，c≠d）并交换它们。
你可以执行任意次数的操作。给定矩阵a和矩阵b，你的任务是确定是否可以使用给定的操作将矩阵a转换为矩阵b。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。
每个测试用例的第一行包含两个整数n和m（1≤n,m≤n*m≤2*10^5）——矩阵的大小。
接下来n行，每行m个整数a_ij（1≤a_ij≤n*m），保证矩阵a是排列。
接下来n行，每行m个整数b_ij（1≤b_ij≤n*m），保证矩阵b是排列。
保证所有测试用例的n*m值之和不超过2*10^5。

输出数据格式：
对于每个测试用例，如果可以通过给定操作将矩阵a转换为矩阵b，则输出"YES"，否则输出"NO"。
每个字母的大小写都可以（小写或大写）。例如，"yEs"、"yes"、"Yes"和"YES"都将被接受为肯定答案。题目大意： 给定一个n行m列的矩阵a，包含1到n*m的整数排列。可以通过以下两种操作将矩阵a转换为矩阵b： 1. 选择两列c和d（1≤c,d≤m，c≠d）并交换它们； 2. 选择两行c和d（1≤c,d≤n，c≠d）并交换它们。 你可以执行任意次数的操作。给定矩阵a和矩阵b，你的任务是确定是否可以使用给定的操作将矩阵a转换为矩阵b。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含两个整数n和m（1≤n,m≤n*m≤2*10^5）——矩阵的大小。 接下来n行，每行m个整数a_ij（1≤a_ij≤n*m），保证矩阵a是排列。 接下来n行，每行m个整数b_ij（1≤b_ij≤n*m），保证矩阵b是排列。 保证所有测试用例的n*m值之和不超过2*10^5。 输出数据格式： 对于每个测试用例，如果可以通过给定操作将矩阵a转换为矩阵b，则输出"YES"，否则输出"NO"。 每个字母的大小写都可以（小写或大写）。例如，"yEs"、"yes"、"Yes"和"YES"都将被接受为肯定答案。