Tests for problem D

给一棵 $n$ 个点的树，构造 $n$ 个区间，要求每个端点都是 $[1,2n]$ 中的整数且不重复，并使得两个点 $i,j$ 在树上有边，当且仅当区间 $i,j$ 相交且不包含。

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: 1. both endpoints of each segment are integers from $ 1 $ to $ 2n $ , and each integer from $ 1 $ to $ 2n $ should appear as an endpoint of exactly one segment; 2. all segments are non-degenerate; 3. for each pair $ (i, j) $ such that $ i \ne j $ , $ i \in [1, n] $ and $ j \in [1, n] $ , the vertices $ i $ and $ j $ are connected with an edge if and only if the segments $ i $ and $ j $ intersect, but neither segment $ i $ is fully contained in segment $ j $ , nor segment $ j $ is fully contained in segment $ i $ . 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