Kelia is a girl who loves high-dimensional spaces (not really).

Today, she unexpectedly obtained a tree with $n$ nodes, labeled from $1$ to $n$, where the weight of every edge is $1$. Let $d(i, j)$ be the distance between node $i$ and node $j$ in the tree.

Because the tree exists in three-dimensional space, Kelia is unhappy. She wants to embed this tree into an $m$-dimensional space. Specifically, she wants to find $n$ points $x_1, \dots, x_n$ in $m$-dimensional space, where the coordinates of the $i$-th point are $(x_{i,1}, \dots, x_{i,m})$. The distance between $x_i$ and $x_j$ is defined as $\sum_{k=1}^m |x_{i,k}-x_{j,k}|$, which is the Manhattan distance. Kelia wants the distance between $x_i$ and $x_j$ to be equal to $d(i, j)$ for all pairs $(i, j)$.

However, maintaining a high-dimensional space is time-consuming and exhausting, even for Kelia. Therefore, she wants to find the minimum $m$ such that she can find $n$ points satisfying the condition.

Input

The first line contains a positive integer $n (n > 1)$, representing the number of nodes.

The next $n-1$ lines each contain two integers $i, j$, representing an edge in the tree.

Output

If there is no $m \leq 100$ that satisfies the condition, output a single integer $-1$.

Otherwise, output a positive integer $m (1 \leq m \leq 100)$ on the first line, representing the minimum dimension of the space.

Then, output $n$ lines, each containing $m$ space-separated integers $x_{i,j}$, representing the coordinates of the $i$-th point. You must ensure $|x_{i,j}| \leq 100$.

If there are multiple solutions, you may output any one of them. It is guaranteed that if a solution exists, there is a solution where $|x_{i,j}| \leq 100$.

Subtasks

This problem consists of 3 subtasks. You must pass all test cases in a subtask to receive the points for that subtask:

Subtask 1 (8 points): $n \leq 100$, the $i$-th edge connects $1$ and $i$.

Subtask 2 (41 points): $n \leq 100$, the $i$-th edge connects $\lceil \frac{i}{2} \rceil$ and $i+1$.

Subtask 3 (51 points): $n \leq 100$.

Examples

Input 1

5
1 2
1 3
3 4
3 5

Output 1

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