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:
- 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} < t_i$.
- 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.Input
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.Output
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.Exampleinput
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
Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
vector<edge> edges;
vector<vector<int>> g;
int n;
graph(int _n) : n(_n) {
g.resize(n);
}
virtual int add(int from, int to, T cost) = 0;
};
template <typename T>
class forest : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
forest(int _n) : graph<T>(_n) {
}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
assert(id < n - 1);
g[from].push_back(id);
g[to].push_back(id);
edges.push_back({from, to, cost});
return id;
}
};
template <typename T>
class dfs_forest : public forest<T> {
public:
using forest<T>::edges;
using forest<T>::g;
using forest<T>::n;
vector<int> pv;
vector<int> pe;
vector<int> order;
vector<int> pos;
vector<int> end;
vector<int> sz;
vector<int> root;
vector<int> depth;
vector<T> dist;
dfs_forest(int _n) : forest<T>(_n) {
}
void init() {
pv = vector<int>(n, -1);
pe = vector<int>(n, -1);
order.clear();
pos = vector<int>(n, -1);
end = vector<int>(n, -1);
sz = vector<int>(n, 0);
root = vector<int>(n, -1);
depth = vector<int>(n, -1);
dist = vector<T>(n);
}
void clear() {
pv.clear();
pe.clear();
order.clear();
pos.clear();
end.clear();
sz.clear();
root.clear();
depth.clear();
dist.clear();
}
private:
void do_dfs(int v) {
pos[v] = (int) order.size();
order.push_back(v);
sz[v] = 1;
for (int id : g[v]) {
if (id == pe[v]) {
continue;
}
auto &e = edges[id];
int to = e.from ^ e.to ^ v;
depth[to] = depth[v] + 1;
dist[to] = dist[v] + e.cost;
pv[to] = v;
pe[to] = id;
root[to] = (root[v] != -1 ? root[v] : to);
do_dfs(to);
sz[v] += sz[to];
}
end[v] = (int) order.size() - 1;
}
void do_dfs_from(int v) {
depth[v] = 0;
dist[v] = T{};
root[v] = v;
pv[v] = pe[v] = -1;
do_dfs(v);
}
public:
void dfs(int v, bool clear_order = true) {
if (pv.empty()) {
init();
} else {
if (clear_order) {
order.clear();
}
}
do_dfs_from(v);
}
void dfs_all() {
init();
for (int v = 0; v < n; v++) {
if (depth[v] == -1) {
do_dfs_from(v);
}
}
assert((int) order.size() == n);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
dfs_forest<int> g(n);
vector<int> deg(n);
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
--x; --y;
g.add(x, y);
++deg[x];
++deg[y];
}
g.dfs(0);
vector<vector<int>> children(n);
for (int i = 1; i < n; i++) {
children[g.pv[i]].push_back(i);
}
vector<int> num(n, -1);
vector<int> low(n, -1);
for (int i : g.order) {
int sz = (int) children[i].size();
int from = (i == 0 ? -1 : max(0, num[i] - sz));
low[i] = from;
int x = from;
for (int j : children[i]) {
if (x == num[i]) {
++x;
}
num[j] = x++;
}
}
vector<vector<int>> go(n);
for (int i = 0; i < n; i++) {
go[i].resize(deg[i]);
}
go[0].resize(deg[0] + 1);
for (int i = 1; i < n; i++) {
int j = g.pv[i];
int t = num[i];
go[i][t - low[i]] = j;
go[j][t - low[j]] = i;
}
vector<pair<int, int>> res;
res.emplace_back(0, 0);
while (res.back().second >= 0) {
int i = res.back().first;
int t = res.back().second;
int pos = t - low[i];
if (pos >= (int) go[i].size()) {
res.emplace_back(i, low[i]);
continue;
}
res.emplace_back(go[i][pos], t + 1);
}
res.pop_back();
cout << res.size() << '\n';
for (auto& p : res) {
cout << p.first + 1 << " " << p.second << '\n';
}
return 0;
}
