← 返回题目列表

Codeforces · 1714/F

F. 建造一棵树,就是这样

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

树是无环的连通无向图。请注意,在这个问题中,我们讨论的是无根树。

给您四个正整数 $$$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