F. Равный разворот
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

  • Выберите два индекса $$$l$$$ и $$$r$$$ такие, что $$$1 \le l \le r \le n$$$ и $$$a_l = a_r$$$. После этого разверните подотрезок с $$$l$$$-го по $$$r$$$-й элемент, то есть замените $$$[a_l, a_{l + 1}, \ldots, a_{r - 1}, a_r]$$$ на $$$[a_r, a_{r-1}, \ldots, a_{l+1}, a_l]$$$.

Вам также дан массив $$$b$$$ длины $$$n$$$, который является перестановкой $$$a$$$. Найдите последовательность из не более чем $$$n^2$$$ операций, которая превращает массив $$$a$$$ в $$$b$$$, или определите, что такого массива не существует.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 500$$$) — длину массивов $$$a$$$ и $$$b$$$.

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

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

Гарантируется, что $$$b$$$ является перестановкой $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$500$$$.

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

Для каждого набора входных данных выведите «NO» (без кавычек), если невозможно превратить $$$a$$$ в $$$b$$$, используя не более $$$n^2$$$ операций.

Иначе выведите «YES» (без кавычек). Затем выведите целое число $$$k$$$ ($$$0 \leq k \leq n^2$$$) — число операций, которое вы сделаете. Обратите внимание, что вам не нужно минимизировать число операций.

Затем выведите $$$k$$$ строк. В $$$i$$$-й строке выведите два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — индексы для $$$i$$$-й операции.

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

Если существуют несколько решений, выведите любое из них.

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

В первом примере можно выполнить следующие операции: $$$$$$[1,2,4,3,1,2,1,1] \xrightarrow[l=5,\,r=8]{} [1,2,4,3,1,1,2,1] \xrightarrow[l=1,\,r=6]{} [1,1,3,4,2,1,2,1].$$$$$$

Во втором примере можно выполнить следующие операции: $$$$$$[1,2,3,1,3,2,3] \xrightarrow[l=1,\,r=4]{} [1,3,2,1,3,2,3] \xrightarrow[l=3,\,r=6]{} [1,3,2,3,1,2,3].$$$$$$

Можно показать, что в третьем и четвертом примерах нельзя превратить $$$a$$$ в $$$b$$$.