我们在为问题 D 生成测试时遇到了非常困难的时间。为了准备强大的测试,我们必须解决以下问题。
给定一个由 $$$n$$$ 个顶点组成的无向标记树,找到一组线段,使得:
1. 每个线段的两个端点都是从$$$1$$$到$$$2n$$$的整数,并且从$$$1$$$到$$$2n$$$的每个整数应该恰好是一个线段的端点;
2. 所有段都是非退化的;
3. 对于每对 $$$(i, j)$$$,使得 $$$i \ne j$$$、$$$i \in [1, n]$$$ 和 $$$j \in [1, n]$$$,顶点 $$$i$$$ 和 $$$j$$$ 通过边连接当且仅当线段 $$$i$$$ 和 $$$j$$$相交,但线段 $$$i$$$ 均未完全包含在线段 $$$j$$$ 中,线段 $$$j$$$ 也未完全包含在线段 $$$i$$$ 中。
这个问题你也能解决吗?
输入
第一行包含一个整数 $$$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$$$ 条边的端点。
保证给定的图是一棵树。
输出
打印 $$$n$$$ 整数对,第 $$$i$$$ 对应包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le 2n$$$) — 第 $$$i$$$ 段的端点。您打印的所有 $$$2n$$$ 整数应该是唯一的。
保证答案始终存在。
示例
输入 #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