Given a tree with vertices, find an integer point for each node (, , , ) and connect the and with a line segment for each edge , such that:

1. No two points coincide.
2. No two line segments have common points except at both endpoints.
3. There exists a line such that the shape formed by the points is symmetric about the line and the shape formed by the line segments is symmetric about the line.

输入描述:

There are multiple test cases. The first line of input contains an integer (), the number of test cases. For each test case:

The first line contains an integer  (), the number of vertices of the tree.

Each of the following  lines contains two integers  and (, , ), denoting an edge connecting  and .

Note that there are no constraints related to the sum of .

输出描述:

For each test case:

If there is no answer, output the “NO” in the only line.

Otherwise, output “YES“ in the first line, and two integers ,  () in the -th of the following  lines.

In the  -th line, output three integers , ,  (,,), denoting that the shapes are symmetric about the .

If there are multiple answers, output any of them.

5
4
3 2
1 3
4 1
4
2 4
1 4
3 4
9
9 7
4 9
8 4
4 6
1 8
2 6
5 1
3 4
10
5 3
4 5
6 4
2 5
5 8
4 9
7 8
1 2
10 6
7
2 7
7 4
7 5
6 2
4 3
2 1

YES
1 0
-2 0
-1 0
2 0
1 0 0
YES
1 0
0 1
-1 0
0 0
1 0 0
YES
0 3
-2 0
0 0
0 1
0 4
-1 0
2 0
0 2
1 0
1 0 0
NO
NO