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$.

鸭子Quack有一个长度为 $n$ 的排列$^{\text{∗}}$ $a$ 和一个不完整的序列 $b_1,b_2,\ldots,b_n$。

$b$ 中的每个元素要么是 $-1$，要么是 $1$ 到 $n$ 之间的整数。$1$ 到 $n$ 中的每个整数在 $b$ 中至多出现一次。

Quack 希望将 $b$ 补充完整，使其成为一个与 $a$ 可交换的排列。换言之，在将 $b$ 中所有 $-1$ 替换为适当值后，应对每个 $1 \le i \le n$ 满足等式 $a_{b_i}=b_{a_i}$。

幽灵Ja 想帮助 Quack。在所有可能的 $b$ 的补全方案中，他希望找到字典序最小$^{\text{†}}$ 的那个。

请判断是否存在这样的补全方案。若存在，输出字典序最小的有效排列 $b$；否则，报告该问题无解。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中 $n$ 个互不相同的整数组成的任意顺序的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

$^{\text{†}}$ 当且仅当满足以下条件时，数组 $p$ 字典序小于同长度的数组 $q$：

• $p \ne q$，且在 $p$ 与 $q$ 首次不同的位置上，$p$ 在该位置的元素比 $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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

保证 $b$ 中每个 $1$ 到 $n$ 的整数至多出现一次。

保证所有测试用例的 $n$ 之和不超过 $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$.

对于每个测试用例，若答案存在，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出答案（大写或小写）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答。

如果答案存在，则在下一行输出 $n$ 个整数 $p_1,p_2,\ldots,p_n$ —— 即在将 $b$ 中所有 $-1$ 替换后得到的字典序最小的有效序列。

序列 $p$ 必须是一个排列，即 $1$ 到 $n$ 中的每个整数在 $p$ 中必须恰好出现一次。此外，它还必须满足对每个 $1 \le i \le n$，均有 $a_{p_i}=p_{a_i}$。

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.

在第一个测试用例中，$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$，不存在合法的补全方案。