We had a really tough time generating tests for problem D. In order to prepare strong tests, we had to solve the following problem.
Given an undirected labeled tree consisting of $$$n$$$ vertices, find a set of segments such that:
Can you solve this problem too?
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of vertices in the tree.
Then $$$n - 1$$$ lines follow, each containing two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) denoting the endpoints of the $$$i$$$-th edge.
It is guaranteed that the given graph is a tree.
Print $$$n$$$ pairs of integers, the $$$i$$$-th pair should contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i < r_i \le 2n$$$) — the endpoints of the $$$i$$$-th segment. All $$$2n$$$ integers you print should be unique.
It is guaranteed that the answer always exists.
6 1 2 1 3 3 4 3 5 2 6
9 12 7 10 3 11 1 5 2 4 6 8
1
1 2
Name |
---|