8599: Symmetry: Tree

给定一棵包含nn个顶点的树，找到一个整数点p_i=(x_i,y_i)我x = (我y我)对于每个节点ii (i=1i= 1,22， \cdots⋯，nn)并连接p_upu和p_vpv对每条边(u,v)(u,v)设置一条线段，使:
1. 没有两点重合。

2. 没有两条线段除了两端以外有公共点。

3.存在一条直线，这些点形成的形状关于这条直线是对称的，线段形成的形状关于这条直线也是对称的

有多个测试用例。第一行输入为整数TT(1\le T\le 10^31≤T≤10)

3.

)，测试用例的数量。对于每个测试用例:



第一行包含一个整数nn (1\le n\le10^31≤n≤10)

3.

)，树的顶点数。



下面的n-1n−1行包含两个整数uu和vv(1\le u1≤u, v\le nv≤n, u\ne vu)





=v)，表示一条连接uu和vv的边。



注意，没有与nn和相关的约束。

对于每个测试用例:



如果没有回答，则在唯一一行输出“no”。



否则，在第一行输出“YES”和两个整数x_ix

我



, y_iy

我



(0 \ le | x_i | |, y_i | \ le n0≤∣x

我



∣∣y

我



以下n行第ii行中≤n)。



在(n+2)(n+2)第一行中，输出三个整数aa, bb, cc (0\le |a|0≤∣a∣，|b|∣b∣，|c|\le n∣c∣≤n)，表示形状围绕ax+by+c=0ax+by+c=0对称。



如果有多个答案，输出其中任何一个。

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