Codeforces Round 950 (Div. 3) |
---|
Закончено |
У вас была матрица $$$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]]$$$ — нет.
За одну операцию вы можете совершить одно из двух следующих действий:
Вы можете совершить любое количество операций.
Вам даны исходная матрица $$$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» будут приняты как положительный ответ.
71 1112 21 23 44 32 12 21 23 44 31 23 41 5 9 612 10 4 87 11 3 21 5 9 612 10 4 87 11 3 23 31 5 96 4 23 8 79 5 12 4 67 8 32 31 2 65 4 36 1 23 4 51 55 1 2 3 44 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} $$$
Название |
---|