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.
[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.
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≤𝑛≤2⋅105;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 2⋅1052⋅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.
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
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