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;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = 0;
  while (!isdigit(c)) {
    if (c == '-') flag = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  x = flag ? -x : x;
}
template <class T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 5e5 + 10;
const int mod = 998244353;
struct Edge {
  int next, ed;
};
Edge e[maxn * 2];
int head[maxn], cnt;
void addEdge(int st, int ed) {
  e[cnt].ed = ed;
  e[cnt].next = head[st];
  head[st] = cnt++;
}
bool vis[maxn];
int sum[maxn], d[maxn];
int ansl[maxn], ansr[maxn];
void get(int k) {
  sum[k] = 1;
  for (int i = head[k]; i != -1; i = e[i].next) {
    int ed = e[i].ed;
    if (sum[ed] == 0) {
      get(ed);
      sum[k] += sum[ed];
      ++d[k];
    }
  }
}
void dfs(int k, int l, int r) {
  vis[k] = 1;
  ansr[k] = l + d[k];
  int c = l, temp = r;
  for (int i = head[k]; i != -1; i = e[i].next) {
    int ed = e[i].ed;
    if (!vis[ed]) {
      ansl[ed] = c;
      ++c;
      dfs(ed, temp - sum[ed] * 2 + 2, temp);
      temp -= sum[ed] * 2 - 1;
    }
  }
}
int main() {
  int n;
  read(n);
  memset(head, -1, sizeof(head));
  for (int i = 1; i < n; ++i) {
    int st, ed;
    scanf("%d %d", &st, &ed);
    addEdge(st, ed);
    addEdge(ed, st);
  }
  get(1);
  ansl[1] = 1;
  dfs(1, 2, n * 2);
  for (int i = 1; i <= n; ++i) {
    printf("%d %d\n", ansl[i], ansr[i]);
  }
}