← 返回题目列表

Codeforces · 1311/E

E. 构造二叉树

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

给你两个整数 $$$n$$$ 和 $$$d$$$。您需要构造一棵由 $$$n$$$ 个顶点组成的有根二叉树,根位于顶点 $$$1$$$ 处,所有顶点的深度总和等于 $$$d$$$。

树是没有循环的连通图。有根树有一个特殊的顶点,称为根。顶点 $$$v$$$ 的父节点是从根到顶点 $$$v$$$ 的路径上与 $$$v$$$ 顶点不同的最后一个顶点。顶点$$$v$$$的深度是从根到顶点$$$v$$$的路径长度。顶点 $$$v$$$ 的子节点都是以 $$$v$$$ 为父节点的所有顶点。二叉树是这样一种树,没有一个顶点拥有超过 $$$2$$$ 子节点。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$2 \le n, d \le 5000$$$) — 树中的顶点数以及所有顶点所需的深度总和。

保证$$$n$$$之和与$$$d$$$之和均不超过$$$5000$$$ ($$$\sum n \le 5000, \sum d \le 5000$$$)。

输出

对于每个测试用例,打印答案。

如果无法构造这样的树,请在第一行打印“NO”(不带引号)。否则,在第一行打印“{YES}”。然后在第二行打印 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$,其中 $$$p_i$$$ 是顶点 $$$i$$$ 的父顶点。请注意,您打印的父级序列应该描述一些二叉树。

示例

输入 #1

3
5 7
10 19
10 18

输出 #1

YES
1 2 1 3 
YES
1 2 3 3 9 9 2 1 6 
NO

注意

示例的第一个和第二个测试用例对应的图片: