CF2237E Permutation Commutation

Quack the Duck has a permutation $ ^{\text{∗}} $ $ a $ of length $ n $ and an incomplete sequence $ b_1,b_2,\ldots,b_n $ . Each element of $ b $ is either $ -1 $ or an integer from $ 1 $ to $ n $ . Each integer from $ 1 $ to $ n $ appears at most once in $ b $ . Quack hopes to complete $ b $ into a permutation that commutes with $ a $ . In other words, after replacing every $ -1 $ in $ b $ , the equality $ a_{b_i}=b_{a_i} $ should hold for every $ 1 \le i \le n $ . Ja the Ghost wants to help Quack. Among all possible ways to complete $ b $ , he wants to find the lexicographically smallest $ ^{\text{†}} $ one. Determine whether such a completion exists. If it exists, output the lexicographically smallest valid permutation $ b $ . Otherwise, report that it is impossible. $ ^{\text{∗}} $ 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). $ ^{\text{†}} $ An array $ p $ is lexicographically smaller than an array $ q $ of the same size if and only if the following holds: - $ p \ne q $ , and in the first position where $ p $ and $ q $ differ, the array $ p $ has a smaller element than the corresponding element in $ q $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the permutation. The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le n $ ) — the permutation $ a $ . The third line of each test case contains $ n $ integers $ b_1,b_2,\ldots,b_n $ ( $ b_i=-1 $ or $ 1 \le b_i \le n $ ) — the incomplete sequence $ b $ . It is guaranteed that each integer from $ 1 $ to $ n $ appears at most once in $ b $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, print "YES" if the answer exists, and "NO" otherwise. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. If the answer exists, in the next line output $ n $ integers $ p_1,p_2,\ldots,p_n $ — the lexicographically smallest valid sequence after replacing every $ -1 $ in $ b $ . The sequence $ p $ must be a permutation, that is, each integer from $ 1 $ to $ n $ must appear exactly once in $ p $ . Also, it must satisfy $ a_{p_i}=p_{a_i} $ for every $ 1 \le i \le n $ .

In the first test case, $ b=[1,2,3] $ commutes with any permutation $ a $ . Since all elements of $ b $ are unknown, this is also the lexicographically smallest possible valid permutation. In the second test case, $ a=[2,1,4,3] $ and $ b_3=4 $ . Since $ a_3=4 $ , the condition for $ i=3 $ gives $ a_{b_3}=b_{a_3} $ , so $ a_4=b_4 $ , hence $ b_4=3 $ . The remaining values are $ 1 $ and $ 2 $ , and the lexicographically smallest valid choice is $ b_1=1 $ , $ b_2=2 $ . Thus the answer is $ [1,2,4,3] $ . In the third test case, $ a=[2,1,4,3] $ , $ b_1=3 $ , and $ b_2=1 $ . For $ i=1 $ , the condition requires $ a_{b_1}=b_{a_1} $ . However, $ a_{b_1}=a_3=4 $ , while $ b_{a_1}=b_2=1 $ . Since $ 4 \neq 1 $ , no valid completion exists.