CF2237E Permutation Commutation

鸭子 Quack 拥有一个长度为 $n$ 的排列 $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$ 的方案中，他希望找到字典序最小的一个。 请判断这样的补全是否存在。如果存在，请输出字典序最小的合法排列 $b$；否则，报告无解。 $^{\text{∗}}$ 长度为 $n$ 的排列是一个包含 $1,2,\ldots,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$。

每组测试包含多个测试用例。第一行包含测试用例个数 $t$（$1\le t\le 10^4$）。各测试用例描述如下。 每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2 \times 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\times 10^5$。

对于每个测试用例，若存在答案则输出 "YES"，否则输出 "NO"（不区分大小写）。 如果存在答案，则在下一行输出 $n$ 个整数 $p_1,p_2,\ldots,p_n$，即将 $b$ 中所有 $-1$ 替换后得到的字典序最小的合法序列。 序列 $p$ 必须是一个排列，即 $1$ 到 $n$ 的每个整数恰好出现一次，并且满足对于每个 $1\le i\le n$，都有 $a_{p_i}=p_{a_i}$。

在第一个测试用例中，$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\ne 1$，无解。 由 ChatGPT 5 翻译