F. Сдвиги и обмены
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны массивы $$$a$$$ и $$$b$$$ длины $$$n$$$ и целое число $$$m$$$.

Массивы содержат только целые числа от $$$1$$$ до $$$m$$$, и оба массива содержат все целые числа от $$$1$$$ до $$$m$$$.

Вы можете многократно выполнять следующие операции над массивом $$$a$$$:

  • циклический сдвиг$$$^{\text{∗}}$$$ массива влево
  • обмен двух соседних элементов, если их разница составляет не менее $$$2$$$.

Возможно ли преобразовать первый массив во второй?

$$$^{\text{∗}}$$$Циклический сдвиг влево массива $$$p$$$ длины $$$n$$$ (в ноль-индексации) — это массив $$$q$$$, такой что $$$q_i = p_{(i + 1) \bmod n}$$$ для всех $$$0 \le i \lt n$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le m \le n \le 5\cdot10^5$$$) — длина массивов и количество различных элементов в $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — массив $$$a$$$.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le m$$$) — массив $$$b$$$.

Гарантируется, что оба массива содержат все целые числа от $$$1$$$ до $$$m$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если возможно преобразовать первый массив во второй, и «NO», если невозможно. Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
8
3 3
1 2 3
3 2 1
4 3
1 1 2 3
1 2 2 3
4 4
1 3 2 4
2 3 4 1
6 3
1 1 2 1 2 3
2 1 1 2 3 1
5 4
2 3 4 1 1
3 2 1 1 4
9 7
2 4 6 7 3 1 5 4 6
6 7 3 5 6 4 2 4 1
9 8
8 3 5 6 5 4 1 7 2
7 5 3 5 8 4 6 2 1
8 6
2 1 5 4 6 3 5 4
6 1 5 2 4 5 3 4
Выходные данные
YES
NO
YES
NO
YES
YES
NO
NO
Примечание

В первом наборе входных данных вы можете преобразовать массив $$$a$$$ в массив $$$b$$$, применив такую последовательность операций:

  • [$$$1$$$, $$$2$$$, $$$3$$$] — сдвиг влево
  • [$$$2$$$, $$$3$$$, $$$1$$$] — обмен индексов $$$2$$$ и $$$3$$$
  • [$$$2$$$, $$$1$$$, $$$3$$$] — сдвиг влево
  • [$$$1$$$, $$$3$$$, $$$2$$$] — сдвиг влево
  • [$$$3$$$, $$$2$$$, $$$1$$$]

Во втором наборе входных данных можно показать, что невозможно преобразовать массив $$$a$$$ в массив $$$b$$$ с помощью данных операций.