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;
long long int pow1(long long int a, long long int b,
                   long long int m = 1000000007) {
  if (b == 0)
    return 1ll;
  else if (b == 1)
    return a;
  else {
    long long int x = pow1(a, b / 2, m);
    x *= x;
    x %= m;
    if (b % 2) {
      x *= a;
      x %= m;
    }
    return x;
  }
}
template <class avgType>
avgType avg(avgType a, avgType b) {
  return (a + b) / 2;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
int randInt() { return rng() % INT_MAX; }
long long int randLL() { return rng64() % LLONG_MAX; }
vector<int> hashmods = {1000000007, 1000000009, 1000000021,
                        1000000033, 1000000087, 1000000093};
struct segNode {
  bool ign;
  int val, aux;
};
template <class segTreeType, class holderType, class helperType>
class LazySegmentTree {
  holderType *st, ignore;
  helperType *arr;

 public:
  LazySegmentTree(holderType *holderarr, helperType *helparr) {
    st = holderarr;
    arr = helparr;
    ignore.ign = 1;
  }
  holderType function(holderType a, holderType b) {
    holderType c;
    c.val = a.val + b.val;
    c.aux = 1;
    c.ign = 0;
    return c;
  }
  void updateVal(int index, segTreeType val) {
    st[index].val = val;
    st[index].aux = 0;
  }
  void init(int a, int index) {
    st[index].val = 1;
    st[index].aux = 1;
  }
  bool auxInfoUpdate(int index) { return (st[index].aux == 0); }
  void resetAux(int index) { st[index].aux = 1; }
  void build(int a, int b, int index) {
    if (a == b) {
      init(a, index);
    } else {
      build(a, avg(a, b), 2 * index);
      build(avg(a, b) + 1, b, 2 * index + 1);
      st[index] = function(st[2 * index], st[2 * index + 1]);
    }
  }
  void update(int a, int b, int index, int l, int r, segTreeType val) {
    if (a > r or b < l) return;
    if (l <= a and b <= r) {
      updateVal(index, val);
    } else {
      if (auxInfoUpdate(index)) {
        update(a, avg(a, b), 2 * index, a, avg(a, b), st[index].aux);
        update(avg(a, b) + 1, b, 2 * index + 1, avg(a, b) + 1, b,
               st[index].aux);
        resetAux(index);
      }
      update(a, avg(a, b), 2 * index, l, r, val);
      update(avg(a, b) + 1, b, 2 * index + 1, l, r, val);
      st[index] = function(st[2 * index], st[2 * index + 1]);
    }
  }
  int query(int a, int b, int index, int l, int r, int val) {
    if (a == b)
      return a;
    else {
      if (auxInfoUpdate(index)) {
        update(a, avg(a, b), 2 * index, a, avg(a, b), st[index].aux);
        update(avg(a, b) + 1, b, 2 * index + 1, avg(a, b) + 1, b,
               st[index].aux);
        resetAux(index);
      }
      if (st[2 * index].val >= val)
        return query(a, avg(a, b), 2 * index, l, r, val);
      else
        return query(avg(a, b) + 1, b, 2 * index + 1, l, r,
                     val - st[2 * index].val);
    }
  }
};
int n, u, v, l[510000], r[510000];
vector<vector<int> > tree(510000);
segNode st[4100000];
void dfs(int index, int par, int start,
         LazySegmentTree<int, segNode, int> *obj) {
  int numchild = tree[index].size();
  if (par > 0) numchild--;
  l[index] = start;
  r[index] = obj->query(1, 2 * n, 1, 1, 2 * n, numchild + 1);
  obj->update(1, 2 * n, 1, l[index], r[index], 0);
  int curr = r[index] - 1;
  for (int neigh : tree[index]) {
    if (neigh == par) continue;
    dfs(neigh, index, curr, obj);
    curr--;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  for (int i = 1; i <= n - 1; i++) {
    cin >> u >> v;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  LazySegmentTree<int, segNode, int> stree(st, NULL);
  stree.build(1, 2 * n, 1);
  stree.update(1, 2 * n, 1, 1, 1, 0);
  dfs(1, -1, 1, &stree);
  for (int i = 1; i <= n; i++) {
    cout << l[i] << " " << r[i] << "\n";
  }
  return 0;
}