← 返回题目列表

Codeforces · 1379/E

E. 逆谱系

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

Ivan 喜欢家谱。目前他正在研究一个由一些人组成的特定家谱结构。在这种结构中,每个人要么指定父母双方,要么没有指定父母。此外,除了一名没有孩子的特殊人士外,每个人都只有一个孩子。此结构中的人员方便地编号为从 $$$1$$$ 到 $$$n$$$,$$$s_i$$$ 表示人员 $$$i$$$ 的孩子(对于没有任何孩子的人,$$$s_i = 0$$$)。

如果 $$$a = b$$$,或者 $$$a$$$ 有一个孩子,并且该孩子是 $$$b$$$ 的祖先,我们就说 $$$a$$$ 是 $$$b$$$ 的祖先。也就是说 $$$a$$$ 是 $$$a$$$、$$$s_a$$$、$$$s_{s_a}$$$ 等的祖先。

如果这个人指定了双亲,并且其中一个父母的祖先总数至少是另一个的两倍,我们就说这个人 $$$i$$$ 是不平衡的。

Ivan 统计了结构中不平衡的人数,总共得到了 $$$k$$$ 人。然而,他不确定自己的计算是否正确,并且想检查是否至少存在一种结构,其中 $$$n$$$ 人总共有 $$$k$$$ 不平衡的人。请帮助他找到一个这样的结构,或者确定它是否不存在。

输入

输入包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 100\,000$$$, $$$0 \leq k \leq n$$$)、总人数和失衡人数。

输出

如果没有$$$n$$$人和$$$k$$$不平衡人员的构造,则输出NO。

否则在第一行输出 YES,然后 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \leq s_i \leq n$$$),它描述构造并指定每个节点的子节点(如果该人没有任何子节点,则为 0)。

示例

输入 #1

3 0

输出 #1

YES
0 1 1

输入 #2

5 1

输出 #2

YES
0 1 1 3 3

输入 #3

3 2

输出 #3

NO

注意

在第一个示例中,一个人可以拥有 3 人的结构,其中 1 人有 2 个父母。

在第二个示例中,可以使用以下结构:

只有人 1 是不平衡的,因为他们的父母之一总共有 1 个祖先,而另一个父母有 3 个祖先。