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.

输入输出样例

输入样例 #1

6
1 2
1 3
3 4
3 5
2 6

输出样例 #1

9 12
7 10
3 11
1 5
2 4
6 8

输入样例 #2

1

输出样例 #2

1 2

题意翻译

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