Problem: We had a really tough time generating tests for problem D. In order to prepare strong tests, we had to solve the following problem.

Given an undirected labeled tree consisting of n vertices, find a set of segments such that:

  1. both endpoints of each segment are integers from 1 to 2n, and each integer from 1 to 2n should appear as an endpoint of exactly one segment; 
  2. all segments are non-degenerate; 
  3. for each pair (i, j) such that i ≠ j, i ∈ [1, n] and j ∈ [1, n], the vertices i and j are connected with an edge if and only if the segments i and j intersect, but neither segment i is fully contained in segment j, nor segment j is fully contained in segment i. 



Can you solve this problem too?

Input

The first line contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5) — the number of vertices in the tree.

Then n - 1 lines follow, each containing two integers x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i) denoting the endpoints of the i-th edge.

It is guaranteed that the given graph is a tree.

Output

Print n pairs of integers, the i-th pair should contain two integers l_i and r_i (1 ≤ l_i < r_i ≤ 2n) — the endpoints of the i-th segment. All 2n integers you print should be unique.

It is guaranteed that the answer always exists.

Examples

Input


6
1 2
1 3
3 4
3 5
2 6


Output


9 12
7 10
3 11
1 5
2 4
6 8


Input


1


Output


1 2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  std::cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const long long hell = round(1e12);
vector<long long> ch;
vector<pair<long long, long long>> a;
long long calc_child(vector<vector<long long>>& v, long long cur,
                     long long par) {
  long long c = 0;
  for (auto x : v[cur]) {
    if (x == par) continue;
    c++;
    calc_child(v, x, cur);
  }
  ch[cur] = c;
  return 0;
}
long long make_seg(vector<vector<long long>>& v, long long cur, long long par,
                   long long st, long long en) {
  en = en + 1 + ch[cur];
  a[cur] = {st, en};
  long long i = 1;
  long long curen = en;
  for (auto x : v[cur]) {
    if (x == par) continue;
    en = make_seg(v, x, cur, curen - i, en);
    i++;
  }
  return en;
}
signed solve() {
  long long n;
  cin >> n;
  vector<vector<long long>> v(n + 1, vector<long long>(0));
  ch.resize(n + 1);
  a.resize(n + 1);
  for (long long i = 0; i < n - 1; i++) {
    long long a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  calc_child(v, 1, 0);
  long long l = 1;
  long long en = l;
  make_seg(v, 1, 0, l, en);
  for (long long i = 1; i <= n; i++)
    cout << a[i].first << " " << a[i].second << endl;
  return 0;
}
signed main() {
  long long t = 1;
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  while (t--) {
    solve();
  }
  return 0;
}