← 返回题目列表

Codeforces · 1340/D

D. 娜斯佳和时间机器

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

丹尼斯来到娜斯佳身边,发现她见到他并不高兴……她只有一次机会变得快乐。丹尼斯想买娜斯佳喜欢的所有东西,所以她一定会同意和他谈谈。

他们居住的城市地图上有很多广场,其中一些广场之间有道路相连。每对方块之间恰好有一条路,不会两次访问任何顶点。原来,城市的图是一棵树。

Denis 在 $$$0$$$ 时刻位于顶点 $$$1$$$。他想至少访问每个顶点一次并尽快返回。

丹尼斯可以在 $$$1$$$ 时间内走完一条路。不幸的是,这座城市太大了,要参观完所有广场需要很长时间。于是,丹尼斯迈出了孤注一掷的一步。他拿出他在地下室建造的袖珍时光机。在它的帮助下,丹尼斯可以将时间更改为任何非负时间,该时间小于当前时间。

但是时间机器有一个特点。如果英雄发现自己在同一时间两次出现在同一个地方,就会出现普遍比例的爆炸,而娜斯佳会一直不高兴。因此,丹尼斯要求你使用时间机器为他找到一条路线,他将绕过所有方格并返回到第一个方格,同时他访问任何方格的最大时间将是最小的。

形式上,Denis 的路线可以表示为一系列对:$$$\{v_1, t_1\}, \{v_2, t_2\}, \{v_3, t_3\}, \ldots, \{v_k, t_k\}$$$,其中 $$$v_i$$$ 是平方数,$$$t_i$$$ 是男孩现在所处的时间。

必须满足以下条件:

- 路线在 $$$0$$$ 时刻从方格 $$$1$$$ 开始,即 $$$v_1 = 1,t_1 = 0$$$,并在方格 $$$1$$$ 结束,即 $$$v_k = 1$$$。
- 所有转换分为两种类型: 在正方形中改变时间:$$$\{ v_i, t_i \} \to \{ v_{i+1}, t_{i+1} \} : v_{i+1} = v_i, 0 \leq t_{i+1} < t_i$$$。 沿着其中一条路行走:$$$\{ v_i, t_i \} \to \{ v_{i+1}, t_{i+1} \}$$$。至此,$$$v_i$$$ 和 $$$v_{i+1}$$$ 有公路连接,$$$t_{i+1} = t_i + 1$$$
- 所有对 $$$\{ v_i, t_i \}$$$ 必须不同。
- 所有方块都在 $$$v_1, v_2, \ldots, v_k$$$ 之间。

您需要找到一条路线,使得在任何方格中的最大时间都最小,即 $$$\max{(t_1, t_2, \ldots, t_k)}$$$ 为可能的最短路线。

输入

第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — 城市中的正方形数量。

接下来的 $$$n - 1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ $$$(1 \leq v, u \leq n, u \neq v)$$$ - 由道路连接的方块的编号。

保证给定的图是一棵树。

输出

在第一行中输出整数 $$$k$$$ $$$(1 \leq k \leq 10^6)$$$ — Denis 路径的长度。

在接下来的 $$$k$$$ 行中,输出对 $$$v_i, t_i$$$ — 描述 Denis 路线的对(如语句中所示)。

必须满足声明中描述的所有路线要求。

保证在给定的限制下,至少有一条路线和一个长度不超过$$$10^6$$$的答案。如果有多个可能的答案,请打印任何一个。

示例

输入 #1

5
1 2
2 3
2 4
4 5

输出 #1

13
1 0
2 1
3 2
3 1
2 2
4 3
4 1
5 2
5 1
4 2
2 3
2 0
1 1