给定一棵包含 $n$ 个顶点的树，对于每个节点 $i = 1, 2, \dots, n$，请找到一个整点 $p_i = (x_i, y_i)$，然后对于每条边 $(u, v)$，用线段连接点 $p_u$ 和 $p_v$，使得以下条件成立：

1. 没有两个点重合。
2. 除了端点外，没有两条线段有公共点。
3. 存在一条直线，使得由这些点构成的形状关于该直线对称，且由这些线段构成的形状也关于该直线对称。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^3$)，表示树的顶点数。 接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示连接 $u$ 和 $v$ 的一条边。

注意：题目没有关于 $n$ 之和的约束。

输出格式

对于每组测试数据：

如果不存在满足条件的方案，输出一行 "NO"。 否则，第一行输出 "YES"，接下来的 $n$ 行中，第 $i$ 行输出两个整数 $x_i$ 和 $y_i$ ($0 \le |x_i|, |y_i| \le n$)。 之后，再输出一行，包含三个整数 $a, b, c$ ($0 \le |a|, |b|, |c| \le n$)，表示这些形状关于直线 $ax + by + c = 0$ 对称。

如果存在多种答案，输出其中任意一种即可。

样例

样例输入 1

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

样例输出 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