#P1714F. Build a Tree and That Is It

    ID: 7960 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>constructive algorithmsimplementationtrees*1900

Build a Tree and That Is It

Description

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,d23n, d_{12}, d_{23} and d31d_{31}. Construct a tree such that:

  • it contains nn vertices numbered from 11 to nn,
  • the distance (length of the shortest path) from vertex 11 to vertex 22 is d12d_{12},
  • distance from vertex 22 to vertex 33 is d23d_{23},
  • the distance from vertex 33 to vertex 11 is d31d_{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 tt (1t1041 \le t \le 10^4) —the number of test cases in the test.

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

Each test case consists of four positive integers n,d12,d23n, d_{12}, d_{23} and d31d_{31} (3n2105;1d12,d23,d31n13 \le n \le 2\cdot10^5; 1 \le d_{12}, d_{23}, d_{31} \le n-1).

It is guaranteed that the sum of nn values for all test cases does not exceed 21052\cdot10^5.

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

If the answer is positive, print another n1n-1 line each containing a description of an edge of the tree — a pair of positive integers xi,yix_i, y_i, which means that the iith edge connects vertices xix_i and yiy_i.

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

Input

The first line of the input contains an integer tt (1t1041 \le t \le 10^4) —the number of test cases in the test.

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

Each test case consists of four positive integers n,d12,d23n, d_{12}, d_{23} and d31d_{31} (3n2105;1d12,d23,d31n13 \le n \le 2\cdot10^5; 1 \le d_{12}, d_{23}, d_{31} \le n-1).

It is guaranteed that the sum of nn values for all test cases does not exceed 21052\cdot10^5.

Output

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

If the answer is positive, print another n1n-1 line each containing a description of an edge of the tree — a pair of positive integers xi,yix_i, y_i, which means that the iith edge connects vertices xix_i and yiy_i.

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

Samples

样例输入 1

<div class="test-example-line test-example-line-even test-example-line-0">9</div><div class="test-example-line test-example-line-odd test-example-line-1">5 1 2 1</div><div class="test-example-line test-example-line-even test-example-line-2">5 2 2 2</div><div class="test-example-line test-example-line-odd test-example-line-3">5 2 2 3</div><div class="test-example-line test-example-line-even test-example-line-4">5 2 2 4</div><div class="test-example-line test-example-line-odd test-example-line-5">5 3 2 3</div><div class="test-example-line test-example-line-even test-example-line-6">4 2 1 1</div><div class="test-example-line test-example-line-odd test-example-line-7">4 3 1 1</div><div class="test-example-line test-example-line-even test-example-line-8">4 1 2 3</div><div class="test-example-line test-example-line-odd test-example-line-9">7 1 4 1</div><div class="test-example-line test-example-line-odd test-example-line-9"></div>

样例输出 1

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