"Honeycomb Corn" is a famous Hunan dish and a favorite of Yueyue and Jiajia. Since it is called "Honeycomb Corn," the dish naturally consists of many corn kernels, and any two corn kernels can be connected by an edible thread. They observed that if corn kernels are treated as points and threads as edges, each plate of "Honeycomb Corn" forms a tree. They also discovered that the plates used by restaurants to serve "Honeycomb Corn" are generally square. If a Cartesian coordinate system is appropriately established, all corn kernels are placed at grid points (points where both the x-coordinate and y-coordinate are integers), and the lines connecting the corn kernels are straight and do not intersect.

Shortly after returning home, the Chinese New Year is approaching, and Yueyue and Jiajia want to show off their culinary skills to their friends by making a delicious and visually appealing plate of "Honeycomb Corn." But the problem is, how large of a square plate is needed to hold this dish?

Input

The first line of the input contains the number of corn kernels $n$. The following $n-1$ lines each contain two integers $u$ and $v$, representing a thread connecting corn kernels $u$ and $v$.

Output

The output contains $n$ lines, representing the coordinates of corn kernels $1, 2, 3, \dots, n$ in order, using two non-negative integers $x$ and $y$. According to the problem, the side length of the square plate is equal to $\max\{\max_{1 \le i \le n}\{x_i\}, \max_{1 \le i \le n}\{y_i\}\}$.

Examples

Input 1

4
1 2
2 3
2 4

Output 1

0 1
0 0
1 0
1 1

Subtasks

For each test case, if your output is invalid, you receive 0 points; otherwise, you receive at least 1 point. The specific scoring formula is as follows:

Assuming the side length of the reference solution is $Best$ and your side length is $Ans$, your score is:

• $10$, if $Ans \le Best$
• $\lfloor \frac{Best}{Ans} \times 9 \rfloor + 1$, if $Ans > Best$, where $\lfloor \rfloor$ denotes the floor operation.

Note

You can use the checker program to check your output. The format is:

checker TestNo

where TestNo is the test case number. For example, if you have obtained the output corn5.out for data 5, you can use the command:

checker 5

to test whether your output is valid. When executing this command, both corn5.in and corn5.out must exist.

Please properly save your input files *.in and your output files *.out, and back them up in time to avoid accidental deletion.