33798번 - Permutation Recovery 스페셜 저지다국어

There are two hidden permutations $a$ and $b$ of size $n$.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2, 3, 1, 5, 4]$ is a permutation, but $[1, 2, 2]$ is not a permutation ($2$ appears twice in the array), and $[1, 3, 4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

For each $i$ from $1$ to $n$, you are given the values $a_{b_i}$ and $b_{a_i}$. Recover any possible permutations $a$ and $b$, or determine that none exist.

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) --- the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) --- the size of the two permutations.

The second line of each test case contains $n$ integers. The $i$-th of these is $a_{b_i}$ ($1 \le a_{b_i} \le n$). It is guaranteed that these $n$ integers are distinct.

The third line of each test case contains $n$ integers. The $i$-th of these is $b_{a_i}$ ($1 \le b_{a_i} \le n$). It is guaranteed that these $n$ integers are distinct.

It is guaranteed that the sum of $n$ across all test cases is at most $2\cdot 10^5$.

For each test case, the first line of output should contain "YES" if there is a solution, and "NO" otherwise.

If you print "YES", print two additional lines of output:

The first line should contain $n$ integers $a_1, a_2, \cdots a_n$ ($1 \le a_i \le n$) --- a valid permutation $a$.

The second line should contain $n$ integers $b_1, b_2, \cdots b_n$ ($1 \le b_i \le n$) --- a valid permutation $b$.

If there are multiple solutions, you may print any.

The given solution to the first sample case is $a=[2, 1, 3]$, $b=[3, 2, 1]$. This gives $$a_{b_1} = a_3 = 3 \quad\quad a_{b_2} = a_2 = 1 \quad\quad a_{b_3} = a_1 = 2$$ $$b_{a_1} = b_2 = 2 \quad\quad b_{a_2} = b_1 = 3 \quad\quad b_{a_3} = b_3 = 1$$ which matches the input values $a_b=[3, 1, 2]$ and $b_a=[2, 3, 1]$.

In the second sample case, it can be shown that there are no valid permutations $a$ and $b$.