[Solution] Build a Tree and That Is It Codeforces Solution

F. Build a Tree and That Is It

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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,d12,d23$n,d_{12},d_{23}$ and d31$d_{31}$. Construct a tree such that:

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

Output any tree that satisfies all the requirements

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

 above, or determine that no such tree exists.

Input

The first line of the input contains an integer t$t$ (1≤t≤104$1\le t\le {10}^4$) —the number of test cases in the test.

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

Each test case consists of four positive integers n,d12,d23$n,d_{12},d_{23}$ and d31$d_{31}$ (3≤n≤2⋅105;1≤d12,d23,d31≤n−1$3\le n\le 2\cdot {10}^5;1\le d_{12},d_{23},d_{31}\le n-1$).

It is guaranteed that the sum of n$n$ values for all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

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

If the answer is positive, print another n−1$n-1$ line each containing a description of an edge of the tree — a pair of positive integers xi,yi$x_i,y_i$, which means that the i$i$th edge connects vertices xi$x_i$ and yi$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.