CF1340D.Nastya and Time Machine

Denis came to Nastya and discovered that she was not happy to see him... There is only one chance that she can become happy. Denis wants to buy all things that Nastya likes so she will certainly agree to talk to him.

The map of the city where they live has a lot of squares, some of which are connected by roads. There is exactly one way between each pair of squares which does not visit any vertex twice. It turns out that the graph of the city is a tree.

Denis is located at vertex $1$ at the time $0$. He wants to visit every vertex at least once and get back as soon as possible.

Denis can walk one road in $1$ time. Unfortunately, the city is so large that it will take a very long time to visit all squares. Therefore, Denis took a desperate step. He pulled out his pocket time machine, which he constructed in his basement. With its help, Denis can change the time to any non-negative time, which is less than the current time.

But the time machine has one feature. If the hero finds himself in the same place and at the same time twice, there will be an explosion of universal proportions and Nastya will stay unhappy. Therefore, Denis asks you to find him a route using a time machine that he will get around all squares and will return to the first and at the same time the maximum time in which he visited any square will be minimal.

Formally, Denis's route can be represented as a sequence of pairs: ${v_1, t_1}, {v_2, t_2}, {v_3, t_3}, \ldots, {v_k, t_k}$, where $v_i$ is number of square, and $t_i$ is time in which the boy is now.

The following conditions must be met:

• The route starts on square $1$ at time $0$, i.e. $v_1 = 1, t_1 = 0$ and ends on the square $1$, i.e. $v_k = 1$.
• All transitions are divided into two types:
  1. Being in the square change the time: ${ v_i, t_i } \to { v_{i+1}, t_{i+1} } : v_{i+1} = v_i, 0 \leq t_{i+1} \lt t_i$.
  2. Walk along one of the roads: ${ v_i, t_i } \to { v_{i+1}, t_{i+1} }$. Herewith, $v_i$ and $v_{i+1}$ are connected by road, and $t_{i+1} = t_i + 1$
• All pairs ${ v_i, t_i }$ must be different.
• All squares are among $v_1, v_2, \ldots, v_k$.

You need to find a route such that the maximum time in any square will be minimal, that is, the route for which $\max{(t_1, t_2, \ldots, t_k)}$ will be the minimum possible.

丹尼斯来到娜斯佳家，却发现她并不高兴见到他……目前只有一种可能让她开心：丹尼斯打算买下娜斯佳喜欢的所有东西，这样她就一定会答应和他交谈。

他们所居住城市的地图由许多广场构成，其中一些广场由道路相连。任意两个广场之间恰好存在一条不重复经过任何顶点的路径。换言之，该城市的图结构是一棵树。

在时刻 $0$，丹尼斯位于顶点 $1$。他希望至少访问每个顶点一次，并尽快返回起点。

丹尼斯沿一条道路行走耗时为 $1$。然而，城市规模实在太大，若仅靠步行遍历所有广场将耗费极长时间。因此，丹尼斯采取了一个孤注一掷的举措：他掏出了自己在地下室制造的便携式时间机器。借助该装置，丹尼斯可将当前时间回拨至任意一个小于当前时间的非负时刻。

但该时间机器有一个特殊限制：若英雄在同一时刻、同一地点出现两次，便会引发宇宙级大爆炸，娜斯佳也将永远无法开心。因此，丹尼斯请求你为他设计一条借助时间机器的路线，使其能遍历全部广场并最终返回起点 $1$，同时使他在任一广场所处的最大时刻值最小化。

形式上，丹尼斯的路线可表示为一系列二元组：${v_1, t_1}, {v_2, t_2}, {v_3, t_3}, \ldots, {v_k, t_k}$，其中 $v_i$ 表示所在广场编号，$t_i$ 表示此时的时间。

需满足以下条件：

• 路线起始于广场 $1$、时刻 $0$，即 $v_1 = 1,\ t_1 = 0$；且终点也为广场 $1$，即 $v_k = 1$。
• 所有转移分为两类：
  1. 原地改变时间：${ v_i, t_i } \to { v_{i+1}, t_{i+1} }$，满足 $v_{i+1} = v_i$，且 $0 \leq t_{i+1} < t_i$；
  2. 沿道路行走一步：${ 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)}$。

The first line contains a single integer $n$ $(1 \leq n \leq 10^5)$ — the number of squares in the city.

The next $n - 1$ lines contain two integers $u$ and $v$ $(1 \leq v, u \leq n, u \neq v)$ - the numbers of the squares connected by the road.

It is guaranteed that the given graph is a tree.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示城市中广场的数量。

接下来的 $n - 1$ 行每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，且 $u \neq v$）—— 表示由道路相连的两个广场的编号。

保证所给图是一棵树。

In the first line output the integer $k$ $(1 \leq k \leq 10^6)$ — the length of the path of Denis.

In the next $k$ lines output pairs $v_i, t_i$ — pairs that describe Denis's route (as in the statement).

All route requirements described in the statements must be met.

It is guaranteed that under given restrictions there is at least one route and an answer whose length does not exceed $10^6$. If there are several possible answers, print any.

第一行输出整数 $k$（$1 \leq k \leq 10^6$）—— Denis 路径的长度。

接下来 $k$ 行，每行输出一对 $v_i, t_i$，表示 Denis 的路径（格式如题目描述中所述）。

题目描述中所述的所有路径要求均须满足。

在给定约束条件下，保证至少存在一条路径，且其长度不超过 $10^6$。若存在多个可行答案，输出任意一个即可。