1714F · Build a Tree and That Is It

Problem: A tree is a connected undirected graph without cycles. Note that in this problem, we are talking about not rooted trees.

You are given four positive integers $n, d_{12}, d_{23}$ and $d_{31}$. Construct a tree such that:

• it contains $n$ vertices numbered from $1$ to $n$,
• the distance (length of the shortest path) from vertex $1$ to vertex $2$ is $d_{12}$,
• distance from vertex $2$ to vertex $3$ is $d_{23}$,
• the distance from vertex $3$ to vertex $1$ is $d_{31}$.

Output any tree that satisfies all the requirements above, or determine that no such tree exists.

Input Format: The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

This is followed by $t$ test cases, each written on a separate line.

Each test case consists of four positive integers $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$).

It is guaranteed that the sum of $n$ values for all test cases does not exceed $2\cdot10^5$.

Output Format: For each test case, print YES if the suitable tree exists, and NO otherwise.

If the answer is positive, print another $n-1$ line each containing a description of an edge of the tree — a pair of positive integers $x_i, y_i$, which means that the $i$th edge connects vertices $x_i$ and $y_i$.

The edges and vertices of the edges can be printed in any order. If there are several suitable trees, output any of them.