J. Symmetry: Tree
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Given a tree with $$$n$$$ vertices, for each node $$$i = 1, 2, \ldots, n$$$, find an integer point $$$p_i = (x_i, y_i)$$$, and then, for each edge $$$(u, v)$$$, connect points $$$p_u$$$ and $$$p_v$$$ with a line segment, so that the following conditions hold:

  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.
Input

There are multiple test cases. The first line of input contains an integer $$$T$$$ ($$$1\le T\le 10^3$$$), the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^3$$$), the number of vertices of the tree.

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u, v\le n$$$, $$$u \ne v$$$), denoting an edge connecting $$$u$$$ and $$$v$$$.

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

Output

For each test case:

If there is no answer, output the word "NO" on the only line.

Otherwise, output "YES" on the first line, and two integers $$$x_i$$$ and $$$y_i$$$ ($$$0\le |x_i|, |y_i| \le n$$$) in the $$$i$$$-th of the following $$$n$$$ lines.

After that, output another line with three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$0\le |a|$$$, $$$|b|$$$, $$$|c|\le n$$$), denoting that the shapes are symmetric about the $$$ax+by+c=0$$$.

If there are multiple answers, output any one of them.

Example
Input
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
Output
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