← 返回题目列表

Codeforces · 1278/E

E. 问题 D 的测试

中文机器翻译题面 查看原题

我们在为问题 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