트리 이사

정점 $N$개와 간선 $N-1$개로 이루어진 트리 $T$가 주어진다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있고, 간선은 $1$번부터 $(N-1)$번까지 번호가 매겨져 있다.

$T$의 모든 정점을 $D$차원 정수 격자 $\mathbb{Z}^D$ 위의 점으로 이사시키고자 한다. 이때, 이사된 정점들의 위치는 다음 조건을 만족해야 한다.

• $i$번 정점이 이사된 위치를 $(x_{i,1},x_{i,2},\cdots ,x_{i,D})$라 하자. $x_{i,j}$는 정수이다.
• 트리에서 $i$번 정점과 $j$번 정점의 거리 $\text{dist}(i,j)$를 $i$번 정점에서 $j$번 정점으로 가는 경로에 있는 간선의 수로 정의하자.
• 모든 $1\le i<j\le N$에 대해서 $|x_{i,1}-x_{j,1}|+|x_{i,2}-x_{j,2}|+\cdots +|x_{i,D}-x_{j,D}|=\text{dist}(i,j)$여야 한다.

트리를 이사할 수 있는 최소 차원 $D$를 구하고, 조건을 만족하도록 정점들을 이사시키자.

첫째 줄에 트리의 정점 수 $N$이 주어진다. ($2\le N\le 2\, 000$)

이후 $N-1$개의 줄에 걸쳐, 그중 $i$번째 줄에는 트리의 $i$번 간선이 잇는 두 정점 번호가 공백으로 구분되어 주어진다.

첫째 줄에 트리를 이사할 수 있는 최소 차원 $D$를 출력한다.

이후 $N$개의 줄에 걸쳐, 그중 $i$번째 줄에 $D$개의 정수 $x_{i,j}$를 공백으로 구분해 출력한다. ($1\le j\le D$)

$x_{i,j}$는 $i$번 정점이 이사되는 격자점의 $j$번째 좌표를 의미하며 $-10^9\le x_{i,j}\le 10^9$이어야 한다.

트리를 여러 방법으로 이사시킬 수 있는 경우 그중 아무 것이나 출력한다.