题目描述

一棵树是一种没有环的连通无向图。请注意，在此问题中，我们讨论的是无根树。

给定四个正整数 $n,d_{12},d_{23}$ 和 $d_{31}$，构建一棵树，使得：

• 它包含从 $1$ 到 $n$ 编号的 $n$ 个顶点，
• 从顶点 $1$ 到顶点 $2$ 的距离（最短路径的长度）为 $d_{12}$，
• 从顶点 $2$ 到顶点 $3$ 的距离为 $d_{23}$，
• 从顶点 $3$ 到顶点 $1$ 的距离为 $d_{31}$。

输出任何满足上述要求的树，或确定不存在这样的树。

输入格式

输入的第一行包含一个整数 $t(1≤t≤10^4)$，表示测试用例的数量。

接下来是 $t$ 个测试用例，每个测试用例占一行。

每个测试用例包括四个正整数 $n,d_{12},d_{23}$ 和 $d_{31}(3≤n≤2⋅10^5；1≤d_{12},d_{23},d_{31}≤n−1)$。

保证所有测试用例中 $n$ 值的总和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，如果存在适当的树，则打印 YES，否则打印 NO。

如果答案为肯定，则再打印 $n-1$ 行，每行包含树的一条边的描述——一对正整数 $x_i,y_i$，表示第 $i$ 条边连接顶点 $x_i$ 和 $y_i$。

边和顶点的顺序可以任意打印。如果有几棵合适的树，则输出其中任意一棵即可。

测试样例

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

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

样例说明