如果我也被苹果树上掉下来的苹果砸中,我能像牛顿一样擅长物理吗?
为了更好地学习物理,艾因想要建造一棵苹果树,这样她就可以被上面的苹果击中。她的苹果树有 $$$n$$$ 个节点,根位于 $$$1$$$。她定义了 重量 苹果树 $$$\sum \limits_{i=1}^n \sum \limits_{j=i+1}^n \text{dep}(\operatorname{lca}(i,j))$$$。
这里,$$$\text{dep}(x)$$$ 被定义为从节点 $$$1$$$ 到节点 $$$x$$$ 的唯一最短路径上的边数。 $$$\operatorname{lca}(i, j)$$$ 被定义为唯一节点 $$$x$$$,其最大值为 $$$\text{dep}(x)$$$,并且出现在路径 $$$(1, i)$$$ 和 $$$(1, j)$$$ 上。
艾恩从一些旧书里读到,她知道牛顿苹果树的重量约为 $$$k$$$,但其确切值已丢失。
作为 Ain 的朋友,你想为她建造一棵有 $$$n$$$ 个节点的苹果树,你的树的重量和 $$$k$$$ 之间的绝对差应该是 最多 $$$1$$$,即 $$$|\text{weight} - k| \le 1$$$。不幸的是,这并不总是可行,在这种情况下请报告。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个数字 $$$n,k$$$ ($$$2 \le n \le 10^5,0 \le k \le 10^{15}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果存在解决方案,则首先输出 $$$\texttt{Yes}$$$;如果不存在解决方案,则首先输出 $$$\texttt{No}$$$。您可以在任一情况下打印每个字符,例如 $$$\texttt{YES}$$$ 和 $$$\texttt{yEs}$$$ 也将被接受。
如果至少有一个解,则打印 $$$n-1$$$ 行,每行包含两个数字 $$$u,v$$$ $$$(1 \le u,v \le n)$$$ 代表苹果树。
示例
输入复制
52 12 24 05 75 5
输出复制
Yes 1 2 No Yes 1 2 1 3 1 4 Yes 1 3 3 5 4 5 3 2 Yes 1 2 2 3 2 4 2 5
注意
在第一个测试用例中,我们可以检查权重为 $$$0$$$。这满足条件,因为 $$$k = 1$$$,因此绝对差仅为 $$$1$$$。
在第二个测试用例中,不存在解决方案,因为不存在权重为 $$$1、2$$$ 或 $$$3$$$ 的 $$$2$$$ 节点树。