시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 26 | 3 | 2 | 50.000% |
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:
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$.
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.
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