← 返回题目列表

Codeforces · 2107/E

E. 艾因和苹果树

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

如果我也被苹果树上掉下来的苹果砸中,我能像牛顿一样擅长物理吗?

为了更好地学习物理,艾因想要建造一棵苹果树,这样她就可以被上面的苹果击中。她的苹果树有 $$$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)$$$ 代表苹果树。

示例

输入
复制

5
2 1
2 2
4 0
5 7
5 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$$$ 节点树。