丹尼斯来到娜斯佳身边,发现她见到他并不高兴……她只有一次机会变得快乐。丹尼斯想买娜斯佳喜欢的所有东西,所以她一定会同意和他谈谈。
他们居住的城市地图上有很多广场,其中一些广场之间有道路相连。每对方块之间恰好有一条路,不会两次访问任何顶点。原来,城市的图是一棵树。
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