P16357 [BalticOI 2026] Blocks

You have $n$ wooden blocks of $k$ different colors arranged in a line. The colors of the blocks are $c_1, c_2, \dots, c_n$, all between $1$ and $k$. A color is _balanced_ if the average position of blocks with that color is $(n+1)/2$. Note that this number is not necessarily an integer. :::align{center}  ::: For example, if $7$ blocks are arranged in the above way, the average position of color $1$ is $(1 + 4 + 6) / 3 = 11/3$, the average position of color $2$ is $(2 + 3 + 7) / 3 = 4$ and the average position of color $3$ is $5$. Since $(7+1)/2=4$, color $2$ is balanced but colors $1$ and $3$ are not. Can you order the blocks in such a way that all colors are balanced?

The first line contains a single integer $t$: the number of test cases. The following lines describe the test cases, each consisting of two lines as follows: The first line contains two integers $n$ and $k$: the number of blocks and the number of different colors. The second line contains the colors of the blocks $c_1, c_2, \dots, c_n$. There is at least one block of each color.

For each test case, print "`YES`" if a solution exists, and "`NO`" otherwise. If a solution exists, describe one possible order by printing $n$ integers on another line: the color of the block in each position.

### Explanation In the output of the first test case, color $1$ is balanced because its average position is $(1 + 4 + 5 + 6) / 4 = 4$, which equals $(n + 1) / 2$. Similarly, the average position of color $2$ is $(2 + 3 + 7) / 3 = 4$. Both colors are therefore balanced. In the second test case, neither of the two possible orders make the colors balanced. In the output of the third test case, blocks with color $1$ appear at positions $1$ and $2$. The average is $3/2$, so color $1$ is balanced. ### Constraints - $1 \le t \le 100$ - $1 \le k \le n \le 2 \cdot 10^5$ - $1 \le c_1, c_2, \dots, c_n \le k$ - The sum of all $n$ is at most $2 \cdot 10^5$ ### Scoring | Subtask | Constraints | Points | | :-----: | ----------- | :-------: | | 1 | $n \le 3$ | $4$ | | 2 | $n \le 15$ | $13$ | | 3 | There is at most one color that appears an odd number of times | $18$ | | 4 | All colors appear an equal number of times | $23$ | | 5 | $k \le 15$ | $15$ | | 6 | No additional constraints | $27$ |