给定一棵由 $N$ 个顶点和 $N - 1$ 条边组成的树 $T$，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $(N - 1)$。

你需要将 $T$ 的所有顶点移动到 $D$ 维整数网格 $\mathbb{Z}^D$ 上的点。顶点移动到的点必须满足以下条件。

• 设移动后顶点 $i$ 的新位置为 $(x_{i,1}, x_{i,2}, \dots, 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}| + \dots + |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$。

如果存在多种满足条件的移动方案，输出其中任意一种即可。

样例

输入样例 1

5
1 2
1 3
1 4
1 5

输出样例 1

2
0 0
-1 0
1 0
0 -1
0 1