Mastermind
Contest: Codeforces Round 658 (Div. 1)
Difficulty rating: 2500
Tags: constructive algorithms, graph matchings, greedy, implementation, sortings, two pointers

In the game of Mastermind, there are two players  — Alice and Bob. Alice has a secret code, which Bob tries to guess. Here, a code is defined as a sequence of $$$n$$$ colors. There are exactly $$$n+1$$$ colors in the entire universe, numbered from $$$1$$$ to $$$n+1$$$ inclusive.

When Bob guesses a code, Alice tells him some information about how good of a guess it is, in the form of two integers $$$x$$$ and $$$y$$$.

The first integer $$$x$$$ is the number of indices where Bob's guess correctly matches Alice's code. The second integer $$$y$$$ is the size of the intersection of the two codes as multisets. That is, if Bob were to change the order of the colors in his guess, $$$y$$$ is the maximum number of indices he could get correct.

For example, suppose $$$n=5$$$, Alice's code is $$$[3,1,6,1,2]$$$, and Bob's guess is $$$[3,1,1,2,5]$$$. At indices $$$1$$$ and $$$2$$$ colors are equal, while in the other indices they are not equal. So $$$x=2$$$. And the two codes have the four colors $$$1,1,2,3$$$ in common, so $$$y=4$$$.

Solid lines denote a matched color for the same index. Dashed lines denote a matched color at a different index. $$$x$$$ is the number of solid lines, and $$$y$$$ is the total number of lines.

You are given Bob's guess and two values $$$x$$$ and $$$y$$$. Can you find one possibility of Alice's code so that the values of $$$x$$$ and $$$y$$$ are correct?

Input format:
The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$)  — the number of test cases. Next $$$2t$$$ lines contain descriptions of test cases.

The first line of each test case contains three integers $$$n,x,y$$$ ($$$1\le n\le 10^5, 0\le x\le y\le n$$$)  — the length of the codes, and two values Alice responds with.

The second line of each test case contains $$$n$$$ integers $$$b_1,\ldots,b_n$$$ ($$$1\le b_i\le n+1$$$)  — Bob's guess, where $$$b_i$$$ is the $$$i$$$-th color of the guess.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, on the first line, output "YES" if there is a solution, or "NO" if there is no possible secret code consistent with the described situation. You can print each character in any case (upper or lower).

If the answer is "YES", on the next line output $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le n+1$$$)  — Alice's secret code, where $$$a_i$$$ is the $$$i$$$-th color of the code.

If there are multiple solutions, output any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first test case is described in the statement.

In the second test case, $$$x=3$$$ because the colors are equal at indices $$$2,4,5$$$. And $$$y=4$$$ because they share the colors $$$1,1,1,2$$$.

In the third test case, $$$x=0$$$ because there is no index where the colors are the same. But $$$y=4$$$ because they share the colors $$$3,3,5,5$$$.

In the fourth test case, it can be proved that no solution exists.

Example input:
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

Example output:
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

Editorial:
Suppose we have already decided which $$$x$$$ indices agree on color. We should shuffle the remaining $$$n-x$$$ indices in a way that minimizes the number of matches. We should also replace $$$n-y$$$ indices with a color that doesn't contribute to the multiset intersection. Because there are $$$n+1>n$$$ colors, there is some color $$$c$$$ that doesn't appear in $$$a$$$, and we can use it to fill these $$$n-y$$$ indices. Assuming that $$$n-y$$$ is greater than or equal to the minimum number of excess matches we're forced to make, we have a solution.
Let $$$f$$$ be the number of occurrences of the most frequent color in the $$$n-x$$$ indices. Then the number of forced matches is clearly at least $$$2f-(n-x)$$$. And it can be achieved as follows. Let's reindex so that we have contiguous blocks of the same color. Then rotate everything by $$$\left\lfloor \frac{n-x}{2}\right\rfloor$$$ indices.
Now we need to decide on the $$$x$$$ indices that minimize $$$f$$$. This can be done simply by always choosing the most frequent color remaining. We can do this with a priority queue in $$$O(n\log n)$$$, or $$$O(n)$$$ with counting sort.
To make the solution clearer, let's see how it works on the sixth test case in the sample: $$$[3,3,2,1,1,1]$$$ with $$$x=2,y=4$$$. First, we greedily choose the most frequent color two times: $$$[3,\_,\_,1,\_,\_]$$$. After choosing $$$1$$$ the first time, there is a tie between $$$1$$$ and $$$3$$$. So alternatively, we could choose the color $$$1$$$ twice.
Then the remaining indices have colors $$$3,2,1,1$$$. Rotating by $$$(n-x)/2=2$$$ indices, we can place the colors as $$$1,1,2,3$$$ to get $$$[3,1,1,1,2,3]$$$. The color $$$4$$$ does not appear in $$$a$$$, so we should fill $$$n-y=2$$$ indices with $$$4$$$. (But not where we already forced a match.) For example, we get the solution $$$[3,4,1,1,4,3]$$$.