| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 20 | 12 | 12 | 60.000% |
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.
6 3 3 1 2 2 3 1 2 1 2 2 1 5 1 2 3 4 5 1 2 3 4 5 1 1 1 6 4 5 1 2 3 6 1 2 3 4 5 6 10 3 7 5 8 9 1 4 10 6 2 7 8 1 5 10 9 2 3 4 6
YES 2 1 3 3 2 1 NO YES 5 4 3 2 1 5 4 3 2 1 YES 1 1 NO YES 8 2 4 6 1 5 10 7 9 3 10 8 6 1 9 5 3 7 4 2
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$.