P16357 [BalticOI 2026] Blocks

你有 $n$ 个木块，它们共有 $k$ 种不同的颜色，排成一行。木块的颜色依次为 $c_1, c_2, \dots, c_n$，所有颜色均在 $1$ 到 $k$ 之间。 如果某种颜色的所有木块所处位置的平均值等于 $\frac {n + 1} {2}$，则称该颜色是**平衡的**。注意这个数值未必是整数。 :::align{center}  ::: 例如，若 $7$ 个木块按上图方式排列，颜色 $1$ 的平均位置为 $\frac {1 + 4 + 6} {3} = \frac {11} {3}$，颜色 $2$ 的平均位置为 $\frac {2 + 3 + 7} {3} = 4$，颜色 $3$ 的平均位置为 $5$。因为 $\frac {7 + 1} {2} = 4$，所以颜色 $2$ 是平衡的，而颜色 $1$ 和 $3$ 不是。 你能否将这些木块重新排列，使得所有颜色都平衡？

第一行包含一个整数 $t$，表示测试数据的组数。 接下来描述各组测试数据，每组数据由以下两行组成： 第一行包含两个整数 $n$ 和 $k$，表示木块的数量和不同颜色的种数。 第二行包含木块的颜色 $c_1, c_2, \dots, c_n$。每种颜色至少出现一次。

对于每组测试数据，如果存在解，则输出一行 `YES`，否则输出 `NO`。若解存在，再输出一行 $n$ 个整数，描述一种可行的排列，依次表示每个位置上木块的颜色。

### 解释 在第一个样例的输出中，颜色 $1$ 是平衡的，因为其平均位置为 $\frac {1 + 4 + 5 + 6} {4} = 4$，恰好等于 $\frac {n + 1} {2}$。类似地，颜色 $2$ 的平均位置为 $\frac {2 + 3 + 7} {3} = 4$。因此两种颜色都平衡。 在第二个样例中，两种可能的排列均无法使所有颜色平衡。 在第三个样例的输出中，颜色 $1$ 的木块出现在位置 $1$ 和 $2$，其平均值为 $\frac {3} {2}$，因此颜色 $1$ 是平衡的。 ### 数据范围 - $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$ - 所有测试数据 $n$ 的总和不超过 $2 \cdot 10^5$ ### 子任务 | 子任务 | 约束条件 | 分值 | | :---: | --- | :---: | | 1 | $n \le 3$ | $4$ | | 2 | $n \le 15$ | $13$ | | 3 | 至多有一种颜色出现奇数次 | $18$ | | 4 | 所有颜色的出现次数均相等 | $23$ | | 5 | $k \le 15$ | $15$ | | 6 | 无额外限制 | $27$ | 翻译由 DeepSeek V4 Pro 完成