## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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,{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

Solution Click Below:-  👉

👇👇👇👇👇

occupied

above, or determine that no such tree exists.

Input

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\cdot {10}^{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\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$ 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.