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 JAVA):

Solution:
//package cf;
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;
public class USACO {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter (System.out);
        //BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        //StringTokenizer st = new StringTokenizer(reader.readLine()," ");
        int n = Integer.parseInt(reader.readLine());
        HashMap<Integer,List<Integer>> edges = new HashMap<>();
        for (int i=0;i<n;i++) edges.put(i,new ArrayList<>()); 
        for (int i=0;i<n-1;i++) {
        	StringTokenizer st = new StringTokenizer(reader.readLine()," ");
        	int a = Integer.parseInt(st.nextToken())-1;
        	int b = Integer.parseInt(st.nextToken())-1;
        	edges.get(a).add(b);
        	edges.get(b).add(a);
        }
        Stack<Integer> dfs = new Stack<>();
        int[] answer = new int[2*n];
        int count=1;
        /*for (int i=0;i<edges.get(0).size();i++) {
        	answer[count]=edges.get(0).get(i);
        	count++;
        }*/
        int[] dead = new int[n];
        dfs.push(0);
        while (!dfs.isEmpty()) {
        	int k = dfs.pop();
    		if (dead[k]==0) {
        		for (int i=edges.get(k).size()-1;i>=0;i--) {
        			if (dead[edges.get(k).get(i)]==1) edges.get(k).remove(i);
        		}
        		for (int i=0;i<edges.get(k).size();i++) {
        			//System.out.println(k+" "+count);
        			answer[count]=edges.get(k).get(i);
        			count++;
        		}
        		answer[count]=k;
        		count++;
    		}
    		dead[k]=1;
        	if (!edges.get(k).isEmpty()) {
        		dfs.push(k);
        		int m=edges.get(k).get(edges.get(k).size()-1); // next in pushpop
        		edges.get(k).remove(edges.get(k).size()-1);
        		dfs.push(m);
        	}
        }
        int[] reformat = new int[2*n];
        int[] openclose = new int[n];
        for (int i=0;i<2*n;i++) {
        	if (openclose[answer[i]]==0) reformat[2*answer[i]]=i;
        	else reformat[2*answer[i]+1]=i;
        	openclose[answer[i]]++;
        }
        for (int i=0;i<n;i++) {
        	out.println((reformat[2*i]+1)+" "+(reformat[2*i+1]+1));
        }
        reader.close();
        out.close();
    }
}