CF1278E.Tests for problem D

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?

我们为问题 D 构造测试数据时遇到了极大的困难。为了准备强测试数据，我们必须解决如下问题：

给定一棵包含 $n$ 个顶点的无向带标号树，求一组线段，使得：

1. 每条线段的两个端点均为 $1$ 到 $2n$ 之间的整数，且 $1$ 到 $2n$ 中的每个整数恰好作为某一条线段的一个端点出现；
2. 所有线段均为非退化线段（即长度严格大于 0）；
3. 对任意满足 $i \ne j$、$i \in [1, n]$ 且 $j \in [1, n]$ 的数对 $(i, j)$，顶点 $i$ 与 $j$ 在树中相邻当且仅当线段 $i$ 与线段 $j$ 相交，但线段 $i$ 不完全包含于线段 $j$ 内，且线段 $j$ 也不完全包含于线段 $i$ 内。

你也能解决这个问题吗？

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.

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）——树中顶点的数量。

接下来是 $n - 1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，且 $x_i \ne y_i$），表示第 $i$ 条边的两个端点。

保证给定的图是一棵树。

Print $n$ pairs of integers, the $i$-th pair should contain two integers $l_i$ and $r_i$ ($1 \le l_i \lt 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.

输出 $n$ 对整数，其中第 $i$ 对应包含两个整数 $l_i$ 和 $r_i$（满足 $1 \le l_i \lt r_i \le 2n$），即第 $i$ 条线段的两个端点。你所输出的全部 $2n$ 个整数必须互不相同。

保证答案一定存在。