← 返回题目列表

Codeforces · 2237/E

E. 排列交换

中文机器翻译题面 查看原题

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

$$$b$$$ 的每个元素要么是 $$$-1$$$,要么是从 $$$1$$$ 到 $$$n$$$ 的整数。从 $$$1$$$ 到 $$$n$$$ 的每个整数在 $$$b$$$ 中最多出现一次。

Quack 希望将 $$$b$$$ 完成为与 $$$a$$$ 进行交换的排列。换句话说,在替换 $$$b$$$ 中的每个 $$$-1$$$ 后,等式 $$$a_{b_i}=b_{a_i}$$$ 对于每个 $$$1 \le i \le n$$$ 应该成立。

幽灵贾想要帮助嘎嘎。在完成$$$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$$$ 中的相应元素小。

输入

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

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

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印“是“如果答案存在,并且”NO”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

如果答案存在,则在下一行中输出 $$$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}$$$。

示例

输入
复制

12
3
2 3 1
-1 -1 -1
4
2 1 4 3
-1 -1 4 -1
4
2 1 4 3
3 1 -1 -1
4
2 1 4 3
1 -1 -1 2
5
2 3 1 5 4
2 -1 -1 -1 -1
5
2 3 1 5 4
4 -1 -1 -1 -1
6
2 3 1 5 6 4
4 -1 -1 -1 -1 -1
6
2 1 4 3 6 5
-1 3 -1 -1 -1 -1
6
3 5 6 2 1 4
-1 -1 -1 3 6 -1
7
2 3 1 5 4 6 7
-1 -1 -1 -1 -1 7 -1
8
2 3 4 1 6 7 8 5
5 7 -1 -1 -1 -1 -1 -1
8
2 3 4 1 6 7 8 5
5 -1 -1 -1 -1 -1 -1 -1

输出
复制

YES
1 2 3
YES
1 2 4 3
NO
NO
YES
2 3 1 4 5
NO
YES
4 5 6 1 2 3
YES
4 3 1 2 5 6
NO
YES
1 2 3 4 5 7 6
NO
YES
5 6 7 8 1 2 3 4

注意

在第一个测试用例中,$$$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$$$,不存在有效的完成。