A15352. Build a Tree and That Is It

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.

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$ .

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.