← 返回题目列表

Codeforces · 1102/B

B. 数组 K 着色

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

您必须以 $$$k$$$ 颜色为该数组着色,方式如下:

- 数组的每个元素都应该用某种颜色着色;
- 对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$,应该至少有一个元素以数组中的第 $$$i$$$ 颜色着色;
- 对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$,所有以第 $$$i$$$ 颜色着色的元素应该是不同的。

显然,这样的着色可能是不可能的。在这种情况下,打印“NO”。否则打印“YES”和满足上述条件的任何着色(即数字 $$$c_1、c_2、\dots c_n$$$,其中 $$$1 \le c_i \le k$$$ 和 $$$c_i$$$ 是给定数组的第 $$$i$$$ 元素的颜色)。如果有多个答案,您可以打印任何一个。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — 分别是数组 $$$a$$$ 的长度和颜色的数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 5000$$$) — 数组 $$$a$$$ 的元素。

输出

如果没有答案,则打印“NO”。否则,打印“YES”和满足问题陈述中描述的条件的任何着色(即数字 $$$c_1、c_2、\dots c_n$$$,其中 $$$1 \le c_i \le k$$$ 和 $$$c_i$$$ 是给定数组的第 $$$i$$$ 个元素的颜色)。如果有多个答案,您可以打印任何一个。

示例

输入 #1

4 2
1 2 2 3

输出 #1

YES
1 1 2 2

输入 #2

5 2
3 2 1 2 3

输出 #2

YES
2 1 1 2 1

输入 #3

5 2
2 1 1 2 1

输出 #3

NO

注意

在第一个示例中,答案 $$$2~ 1~ 2~ 1$$$ 也是可以接受的。

在第二个例子中,答案 $$$1~ 1~ 1~ 2~ 2$$$ 也是可以接受的。

这两个示例都存在其他可接受的答案。