[Solution] Build a Tree and That Is It solution codeforces

Build a Tree and That Is It solution codeforces – A tree is a connected undirected graph without cycles. Note that in this problem, we are talking about not rooted trees.

Table of Contents

[Solution] Build a Tree and That Is It solution codeforces

You are given four positive integers 𝑛,𝑑12,𝑑23n,d12,d23 and 𝑑31d31. Construct a tree such that:

  • it contains 𝑛n vertices numbered from 11 to 𝑛n,
  • the distance (length of the shortest path) from vertex 11 to vertex 22 is 𝑑12d12,
  • distance from vertex 22 to vertex 33 is 𝑑23d23,
  • the distance from vertex 33 to vertex 11 is 𝑑31d31.

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

Input

The first line of the input contains an integer 𝑡t (1𝑡1041≤t≤104) —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 𝑛,𝑑12,𝑑23n,d12,d23 and 𝑑31d31 (3𝑛2105;1𝑑12,𝑑23,𝑑31𝑛13≤n≤2⋅105;1≤d12,d23,d31≤n−1).

It is guaranteed that the sum of 𝑛n values for all test cases does not exceed 21052⋅105.

[Solution] Build a Tree and That Is It solution codeforces

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

If the answer is positive, print another 𝑛1n−1 line each containing a description of an edge of the tree — a pair of positive integers 𝑥𝑖,𝑦𝑖xi,yi, which means that the 𝑖ith edge connects vertices 𝑥𝑖xi and 𝑦𝑖yi.

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

Example
input

Copy
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

[Solution] Build a Tree and That Is It solution codeforces

output

Copy
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

 

For Solution

Click Here

Leave a Comment