Codeforces 1341F - 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\}\rightarrow\{v_{i+1},t_{i+1}\}:v_{i+1}=v_i$,$\ 0 \le t_{i+1}<t_i$.
  2. Walk along one of the roads: $\{v_i,t_i\}\rightarrow\{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.

Input

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

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

It is guaranteed that the given graph is a tree.

Output

In the first line output the integer $k$ $(1\le k\le 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.

Example

input

5
1 2
2 3
2 4
4 5

output

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

题意

一个树形的结构，每次可以往相邻节点移动，需要花费一单位时间，或者是修改时间为任意非负值，但是不能够两次在同一时间到达同一节点（$\{idx,t\}$的组合必须是惟一的）。问从根节点出发，最后回到根节点所需要的最大时间的最小的时候的遍历方法。如果有多个方法只需要输出任何一种。

思路

可以知道一个事情，遍历整棵树的最大时间，至少为当中所有节点的最大度数：$\max_{v=1}^n \deg v = T$

考虑到任何节点，需要通过该节点$\deg v-1$次来遍历所有邻居然后还需要再通过一次就才能够返回该节点的祖先。那么只要能够构造一种遍历的方法，使得可以满足最大时间为$T$，即满足了题意。考虑对任何一个子树，到达子树$u$的根节点父节点的时候为$t$，子树一共有$k=\deg u -1$个子节点：

情况1： $t+1 \le T-k$，在中途不需要进行时间回溯

$(v,t)\rightarrow(u,t+1)\rightarrow(w_1,t+2)\rightarrow$…$\rightarrow(u,t+2) \rightarrow$…$\rightarrow(w_k,t+k+1)$$\rightarrow$…$\rightarrow(u,t+k) \rightarrow$ $(u,t)$ $\rightarrow$ $(v,t+1)$

情况2：需要进行时间回溯

$(v,t)\rightarrow(u,t+1)\rightarrow(w_1,t+2)\rightarrow$…$\rightarrow(u,t+2)$$\rightarrow\ldots\rightarrow$$(u,T)$ $\rightarrow(u,t^\prime)$ $\rightarrow\ldots$$\rightarrow(w_k,t+k+1)$ $\rightarrow$$\ldots$$\rightarrow(u,t+k)$$\rightarrow(u,t)\rightarrow(v,t+1)$

在代码中backt就是返回父节点的时间，idx为当前的节点下标，t为当前时间节点，fa记录的是父节点的下标。整体进行一遍dfs遍历，按照上述的逻辑进行时间的修改。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int n;
vector<vector<int> > edges;
vector<pair<int,int> > ans;
int maxdeg = 0;

void dfs(int idx, int& t,int backt = -1, int fa = -1){
    ans.push_back(make_pair(idx, t));
    int cnt = edges[idx].size() - (fa == -1? 0: 1);
    for(int to: edges[idx]){
        if(to == fa)
            continue;
        if(t == maxdeg){ // go back
            t = backt - cnt - 1;
            ans.push_back(make_pair(idx, t));
        }
        t++;
        dfs(to, t, t, idx);
        ans.push_back(make_pair(idx, t));
        --cnt;
    }
    if(fa == -1) // root
        return;
    if(t >= backt){
        t = backt - 1;
        ans.push_back(make_pair(idx, t));
    }
    ++t;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    edges = vector<vector<int> >(n+1, vector<int>());
    for(int i=1;i<n;++i){
        int s, e;
        cin>>s>>e;
        edges[s].push_back(e);
        edges[e].push_back(s);
    }

    for(int i=1;i<=n;++i)
        maxdeg = max(maxdeg,(int)edges[i].size());

    int t = 0;
    dfs(1, t);
    cout<< ans.size()<<endl;
    for(auto temp: ans)
        cout << temp.first <<' '<< temp.second <<endl;
}