404692: GYM101611 C Carpet

All cinema stars of Treeland are gathering in its capital to take part in the cinema academy award ceremony. This time organizers decided to prepare something very new for the welcoming part. Their idea is to replace old-fashioned red carpet with a one having a map of Treeland depicted on it.

Treeland consists of n cities connected with n - 1 bidirectional roads in such a way that it is possible to get from any city to any other city. Let us represent the carpet as a rectangular grid of 1 000 000 × 20 unit square cells. Cities should be painted in centers of some cells in such a way that no two cities occupy the same cell. After that roads are painted as segments connecting corresponding cell centers.

To make the carpet beautiful, it was decided to place cities in such a way that no two segments corresponding to roads intersect. This means that no two segments have common points different from their common endpoints.

Some clever mathematician already proved that a solution exists, but unfortunately his proof doesn't provide a way to construct the answer, so this task was assigned to you.

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of cities in Treeland.

Each of the next n - 1 lines contains a pair of integers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) — indices of a road that connects cities u_i and v_i. It is guaranteed that it is possible to get from any city to any other city.

Print n lines. The i-th of these lines should contain two integers x_i and y_i (1 ≤ x_i ≤ 1 000 000, 1 ≤ y_i ≤ 20) — the coordinates of the cell to place the i-th city.

6
1 2
1 3
1 4
4 5
4 6

2 2
1 1
1 3
3 2
4 3
4 1

7
1 2
1 3
2 4
2 5
3 6
3 7

1 1
1 2
2 2
1 3
2 3
3 3
4 3

The picture below illustrates a possible solution for the first sample.