树是无环的连通无向图。请注意,在这个问题中,我们讨论的是无根树。
给您四个正整数 $$$n、d_{12}、d_{23}$$$ 和 $$$d_{31}$$$。构造一棵树,使得:
- 它包含 $$$n$$$ 个顶点,编号从 $$$1$$$ 到 $$$n$$$,
- 从顶点 $$$1$$$ 到顶点 $$$2$$$ 的距离(最短路径的长度)为 $$$d_{12}$$$,
- 从顶点 $$$2$$$ 到顶点 $$$3$$$ 的距离为 $$$d_{23}$$$,
- 从顶点 $$$3$$$ 到顶点 $$$1$$$ 的距离为 $$$d_{31}$$$。
输出任意满足上述所有要求的树,或者确定不存在这样的树。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。
接下来是 $$$t$$$ 测试用例,每个测试用例都写在单独的行上。
每个测试用例由四个正整数 $$$n、d_{12}、d_{23}$$$ 和 $$$d_{31}$$$ ($$$3 \le n \le 2\cdot10^5; 1 \le d_{12}, d_{23}, d_{31} \le n-1$$$) 组成。
保证所有测试用例的$$$n$$$值的总和不超过$$$2\cdot10^5$$$。
输出
对于每个测试用例,如果存在合适的树,则打印 YES,否则打印 NO。
如果答案是肯定的,则打印另一条 $$$n-1$$$ 行,每行包含树的一条边的描述 - 一对正整数 $$$x_i, y_i$$$,这意味着第 $$$i$$$ 条边连接顶点 $$$x_i$$$ 和 $$$y_i$$$。
边缘和边缘的顶点可以按任意顺序打印。如果有多个合适的树,则输出其中任何一个。
示例
输入 #1
9 5 1 2 1 5 2 2 2 5 2 2 3 5 2 2 4 5 3 2 3 4 2 1 1 4 3 1 1 4 1 2 3 7 1 4 1
输出 #1
YES 1 2 4 1 3 1 2 5 YES 4 3 2 5 1 5 5 3 NO YES 2 4 4 1 2 5 5 3 YES 5 4 4 1 2 5 3 5 YES 2 3 3 4 1 3 NO YES 4 3 1 2 2 4 NO