Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Перестановка строк и столбцов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас была матрица $$$a$$$ размера $$$n$$$ на $$$m$$$, содержащая перестановку целых чисел от $$$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» будут приняты как положительный ответ.

Пример
Входные данные
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
Выходные данные
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} $$$