G. Ошибочная сортировка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня Алиса дала Бобу массивы, которые он должен отсортировать по возрастанию. Снова! На данный момент никто точно не знает, сколько раз она это делала.

Бобу даны две последовательности $$$a$$$ и $$$b$$$, обе длиной $$$n$$$. Все целые числа в диапазоне от $$$1$$$ до $$$2n$$$ встречаются ровно один раз в одной из последовательностей $$$a$$$ или $$$b$$$. Другими словами, конкатенированная$$$^{\text{∗}}$$$ последовательность $$$a+b$$$ является перестановкой$$$^{\text{†}}$$$ длины $$$2n$$$.

Боб должен отсортировать обе последовательности по возрастанию одновременно, используя функцию swap Алисы. Функция swap Алисы реализована следующим образом:

  • Даны два индекса $$$i$$$ и $$$j$$$ ($$$i \neq j$$$), она меняет местами $$$a_i$$$ с $$$b_j$$$ и $$$b_i$$$ с $$$a_j$$$.

Учитывая последовательности $$$a$$$ и $$$b$$$, пожалуйста, определите, можно ли отсортировать обе последовательности по возрастанию одновременно после использования функции swap Алисы любое количество раз.

$$$^{\text{∗}}$$$Конкатенированная последовательность $$$a+b$$$ обозначает последовательность $$$[a_1, a_2, a_3, \ldots , b_1, b_2, b_3, \ldots]$$$.

$$$^{\text{†}}$$$Перестановка длины $$$m$$$ содержит все целые числа от $$$1$$$ до $$$m$$$ в каком-то порядке.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 2n$$$).

Третья строка каждого набора входных данных содержит $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \le b_i \le 2n$$$).

Гарантируется, что все целые числа в диапазоне $$$[1,2n]$$$ встречаются ровно один раз в одной из последовательностей $$$a$$$ или $$$b$$$.

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

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

Если возможно отсортировать обе последовательности одновременно, выведите «YES» в новой строке. В противном случае выведите «NO» в новой строке.

Вы можете вывести ответ в любом регистре. Например, строки «yEs», «yes», и «Yes» также будут признаны положительными ответами.

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

В первом наборе входных данных можно показать, что это невозможно.

Во втором наборе входных данных Боб может выполнить одну операцию с индексами $$$i=1$$$ и $$$j=2$$$. Массивы становятся $$$[3,4,5]$$$ и $$$[1,2,6]$$$ соответственно. Оба массива теперь отсортированы.