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:
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String args[]) {new Main().run();}

	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
		work();
		out.flush();
	}
	ArrayList<Integer>[] graph;
	int[][] ret;
	int[] degree;
	int max;
	void work() {
		int n=in.nextInt();
		graph=(ArrayList<Integer>[])new ArrayList[n];
		for(int i=0;i<n;i++) {
			graph[i]=new ArrayList<>();
		}
		ret=new int[n][];
		degree=new int[n];
		for(int i=0;i<n-1;i++) {
			int n1=in.nextInt()-1;
			int n2=in.nextInt()-1;
			graph[n1].add(n2);
			graph[n2].add(n1);
			degree[n1]++;
			degree[n2]++;
		}
		dfs(0,new boolean[n],0);
		for(int i=0;i<n;i++) {
			out.println((ret[i][0]+1)+" "+(ret[i][1]+1));
		}
	}
	private void dfs(int node,boolean[] vis,int cur) {
		vis[node]=true;
		int d=degree[node];
		ret[node]=new int[] {cur,max+d+1};
		int p=max+d;
		max+=d+1;
		for(int nn:graph[node]) {
			if(!vis[nn]) {
				degree[nn]--;
				dfs(nn,vis,p--);
			}
		}
	}
}	



class FastReader
{
	BufferedReader br;
	StringTokenizer st;

	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	public String next() 
	{
		if(st==null || !st.hasMoreElements())
		{
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	public int nextInt() 
	{
		return Integer.parseInt(next());
	}

	public long nextLong()
	{
		return Long.parseLong(next());
	}
}