← 返回题目列表

Codeforces · 1381/C

C. 策划者

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

在 Mastermind 游戏中,有两名玩家 — Alice 和 Bob。爱丽丝有一个密码,鲍勃试图猜测。这里,代码被定义为 $$$n$$$ 颜色的序列。整个宇宙中恰好有$$$n+1$$$种颜色,编号从$$$1$$$到$$$n+1$$$(含)。

当鲍勃猜测一个代码时,爱丽丝以两个整数 $$$x$$$ 和 $$$y$$$ 的形式告诉他一些有关猜测的好坏的信息。

第一个整数 $$$x$$$ 是 Bob 的猜测与 Alice 的代码正确匹配的索引数。第二个整数 $$$y$$$ 是两个代码作为多重集的交集的大小。也就是说,如果 Bob 改变猜测中颜色的顺序,$$$y$$$ 就是他能得到正确的最大索引数。

例如,假设 $$$n=5$$$,Alice 的代码是 $$$[3,1,6,1,2]$$$,Bob 的猜测是 $$$[3,1,1,2,5]$$$。在索引 $$$1$$$ 和 $$$2$$$ 颜色是相等的,而在其他索引中它们不相等。所以$$$x=2$$$。并且这两个代码有四种颜色 $$$1,1,2,3$$$ 的共同点,所以 $$$y=4$$$。

实线表示相同索引的匹配颜色。虚线表示不同索引处的匹配颜色。 $$$x$$$ 是实线数,$$$y$$$ 是总行数。

给你 Bob 的猜测和两个值 $$$x$$$ 和 $$$y$$$。你能找到 Alice 代码的一种可能性,使得 $$$x$$$ 和 $$$y$$$ 的值是正确的吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) — 测试用例的数量。接下来的 $$$2t$$$ 行包含测试用例的描述。

每个测试用例的第一行包含三个整数 $$$n,x,y$$$ ($$$1\le n\le 10^5, 0\le x\le y\le n$$$) — 代码的长度,以及 Alice 响应的两个值。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1,\ldots,b_n$$$ ($$$1\le b_i\le n+1$$$) — Bob 的猜测,其中 $$$b_i$$$ 是猜测的第 $$$i$$$ 颜色。

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

输出

对于每个测试用例,在第一行,如果有解决方案,则输出“YES”,如果没有可能的密码与所描述的情况一致,则输出“NO”。您可以以任何大小写(大写或小写)打印每个字符。

如果答案为“YES”,则在下一行输出 $$$n$$$ 整数 $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le n+1$$$) — Alice 的秘密代码,其中 $$$a_i$$$ 是代码的第 $$$i$$$ 颜色。

如果有多个解,则输出任意一个。

示例

输入 #1

7
5 2 4
3 1 1 2 5
5 3 4
1 1 2 1 2
4 0 4
5 5 3 3
4 1 4
2 3 2 3
6 1 2
3 2 1 1 1 1
6 2 4
3 3 2 1 1 1
6 2 6
1 1 3 2 1 1

输出 #1

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

注意

语句中描述了第一个测试用例。

在第二个测试用例中,$$$x=3$$$ 因为索引 $$$2,4,5$$$ 处的颜色相等。 $$$y=4$$$ 因为它们共享颜色 $$$1,1,1,2$$$。

在第三个测试用例中,$$$x=0$$$ 因为没有颜色相同的索引。但是 $$$y=4$$$ 因为它们共享颜色 $$$3,3,5,5$$$。

在第四个测试用例中,可以证明不存在解。