У Утёнка Кряка есть перестановка$$$^{\text{∗}}$$$ $$$a$$$ длины $$$n$$$ и незаполненная последовательность $$$b_1,b_2,\ldots,b_n$$$.
Каждый элемент $$$b$$$ равен либо $$$-1$$$, либо целому числу от $$$1$$$ до $$$n$$$. Каждое целое число от $$$1$$$ до $$$n$$$ встречается в $$$b$$$ не более одного раза.
Кряк надеется заполнить пропуски в $$$b$$$ так, чтобы она коммутировала с $$$a$$$. Иными словами, после замены каждого $$$-1$$$ в $$$b$$$ равенство $$$a_{b_i}=b_{a_i}$$$ должно выполняться для каждого $$$1 \le i \le n$$$.
Призрак Джа хочет помочь Кряку. Среди всех возможных способов заполнить $$$b$$$ он хочет найти лексикографически наименьший$$$^{\text{†}}$$$.
Определите, существует ли такое заполнение. Если оно существует, выведите лексикографически наименьшую допустимую перестановку $$$b$$$. В противном случае сообщите, что это невозможно.
$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
$$$^{\text{†}}$$$Массив $$$p$$$ лексикографически меньше массива $$$q$$$ такого же размера, если и только если выполняется следующее:
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину перестановки.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — перестановку $$$a$$$.
Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$b_i=-1$$$ или $$$1 \le b_i \le n$$$) — незаполненную последовательность $$$b$$$.
Гарантируется, что каждое целое число от $$$1$$$ до $$$n$$$ встречается в $$$b$$$ не более одного раза.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «YES», если ответ существует, и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Если ответ существует, в следующей строке выведите $$$n$$$ целых чисел $$$p_1,p_2,\ldots,p_n$$$ — лексикографически наименьшую допустимую последовательность после замены каждого $$$-1$$$ в $$$b$$$.
Последовательность $$$p$$$ должна быть перестановкой, то есть каждое целое число от $$$1$$$ до $$$n$$$ должно встречаться в $$$p$$$ ровно один раз. Также она должна удовлетворять условию $$$a_{p_i}=p_{a_i}$$$ для каждого $$$1 \le i \le n$$$.
1232 3 1-1 -1 -142 1 4 3-1 -1 4 -142 1 4 33 1 -1 -142 1 4 31 -1 -1 252 3 1 5 42 -1 -1 -1 -152 3 1 5 44 -1 -1 -1 -162 3 1 5 6 44 -1 -1 -1 -1 -162 1 4 3 6 5-1 3 -1 -1 -1 -163 5 6 2 1 4-1 -1 -1 3 6 -172 3 1 5 4 6 7-1 -1 -1 -1 -1 7 -182 3 4 1 6 7 8 55 7 -1 -1 -1 -1 -1 -182 3 4 1 6 7 8 55 -1 -1 -1 -1 -1 -1 -1
YES1 2 3YES1 2 4 3NONOYES2 3 1 4 5NOYES4 5 6 1 2 3YES4 3 1 2 5 6NOYES1 2 3 4 5 7 6NOYES5 6 7 8 1 2 3 4
В первом наборе входных данных $$$b=[1,2,3]$$$ коммутирует с любой перестановкой $$$a$$$. Поскольку все элементы $$$b$$$ неизвестны, это также лексикографически наименьшая возможная допустимая перестановка.
Во втором наборе входных данных $$$a=[2,1,4,3]$$$ и $$$b_3=4$$$. Так как $$$a_3=4$$$, условие для $$$i=3$$$ даёт $$$a_{b_3}=b_{a_3}$$$, то есть $$$a_4=b_4$$$, откуда $$$b_4=3$$$. Оставшиеся значения — $$$1$$$ и $$$2$$$, и лексикографически наименьший допустимый выбор: $$$b_1=1$$$, $$$b_2=2$$$. Таким образом, ответ — $$$[1,2,4,3]$$$.
В третьем наборе входных данных $$$a=[2,1,4,3]$$$, $$$b_1=3$$$ и $$$b_2=1$$$. Для $$$i=1$$$ условие требует $$$a_{b_1}=b_{a_1}$$$. Однако $$$a_{b_1}=a_3=4$$$, тогда как $$$b_{a_1}=b_2=1$$$. Так как $$$4 \neq 1$$$, допустимого дополнения не существует.
