CF1714F Build a Tree and That Is It
题目描述
树是一个没有环的无向连通图,**注意**,在本题中,我们讨论的是无根树。
现有四个整数 $ n, d_{12}, d_{23} $ 和 $ d_{31} $ . 构建一颗满足以下条件的树:
- 包含从 $ 1 $ 到 $ n $ 的 $n$ 个节点。
- 从节点 $ 1 $ 到节点 $ 2 $ 的距离(最短路的长度)为 $ d_{12} $ 。
- 从节点 $ 2 $ 到节点 $ 3 $ 的距离为 $ d_{23} $ 。
- 从节点 $ 3 $ 到节点 $ 1 $ 的距离为 $ d_{31} $ 。
输出满足条件的任意一棵树;若不存在,输出 `NO`。
输入格式
第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) 表示测试组数。
接下来 $ t $ 组, 每组一行数据包含 $4$ 个整数 $ n, d_{12}, d_{23} $ and $ d_{31} $ ( $ 3 \le n \le 2\cdot10^5; 1 \le d_{12}, d_{23}, d_{31} \le n-1 $ )。
保证 $\sum n \le 2\times 10^5 $ 。
输出格式
对于每一组数据,若存在这种树,输出`YES`;若不存在,输出`NO`.
对于存在的情况,额外输出 $ n-1 $ 行来描述这棵树的边(一对正整数 $ x_i, y_i $ 表示第 $ i $ 条边连接第 $ x_i $ 号节点和第 $ y_i $ 号节点.
你可以按照任何顺序输出这些边及其顶点,若有多种解,输出其中一种即可.