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:
/*********** This template help me to solve the SLOW I/O ***********/ 
 
 
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;
public class Main extends Thread  {
    public static int[] visit;
    public static int max=1;
    public static int[][] arr;
    public static ArrayList<Integer>[] adj; 
    boolean[] prime;
    FastScanner sc;
    PrintWriter pw;
    MathF mf;
    final class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        public long nlo() {
            return Long.parseLong(next());
        }
 
        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }
 
        public int ni() {
            return Integer.parseInt(next());
        }
 
        public String nli() {
            String line = "";
            if (st.hasMoreTokens()) line = st.nextToken();
            else try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            while (st.hasMoreTokens()) line += " " + st.nextToken();
            return line;
        }
 
        public double nd() {
            return Double.parseDouble(next());
        }
    }
    final class MathF {
        long grtdiv(long x)
        {
            if(isPrime(x))
                return 1;
            else
            {
                long ans=0;
                long y=(long)Math.sqrt(x)+1;
                for(;y>=2;y--)
                {
                    if(x%y==0)
                        ans=Math.max(ans,Math.max(y,x/y));
                }
                return ans;
            }
        }
        boolean isPrime(long x)
        {
            for(int i=2;i*i<=x;i++)
            {
                if(x%i==0)
                {
                    return false;
                }
            }
            return true;
        }
        long[][] mul(long[][] arr,long[][] brr,int a,int b,int c,int d)
        {
            long[][] crr=new long[a][d];
            for(int i=0;i<a;i++)
            {
                for(int j=0;j<d;j++)
                {
                    for(int k=0;k<b;k++)
                    {
                        crr[i][j]+=(((arr[i][k]%1000000007)*(brr[k][j]%1000000007))%1000000007);
                    }
                }
            }
            return crr;
        }
        int sod(long a)
        {
            int ans=0;
            while(a!=0)
            {
                ans+=(a%10);
                a=a/10;
            }
            return ans;
        }
        long pow(long a,long b)
        {
            if(b==0)
                return 1;
            else
            {
                long x=pow(a,b/2);
                if(b%2==1)
                    return (x*x*a);
                else
                    return (x*x);
            }
        }
        public  long gcd(long a, long b) {
            return (b == 0 ? a : gcd(b, a % b));
        }
        public long exponent(long a,long b)
        {
            if(b==0)
                return 1;
            else
            {
                long x=exponent(a,b/2);
                x*=x;
                if(b%2==1)
                    x*=a;
                return x;
            }
        }
        public  int nod(long x) {
            int i = 0;
            while (x != 0) {
                i++;
                x = x / 10;
            }
            return i;
        }
 
        public  int nob(long x) {
            if(x==0)
                return 1;
            return (int) Math.floor(Math.log(x) / Math.log(2)) + 1;
        }
 
        public int[] FastradixSort(int[] f) {
            int[] to = new int[f.length];
            {
                int[] b = new int[65537];
                for (int i = 0; i < f.length; i++) b[1 + (f[i] & 0xffff)]++;
                for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
                for (int i = 0; i < f.length; i++) to[b[f[i] & 0xffff]++] = f[i];
                int[] d = f;
                f = to;
                to = d;
            }
            {
                int[] b = new int[65537];
                for (int i = 0; i < f.length; i++) b[1 + (f[i] >>> 16)]++;
                for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
                for (int i = 0; i < f.length; i++) to[b[f[i] >>> 16]++] = f[i];
                int[] d = f;
                f = to;
                to = d;
            }
            return f;
        }
 
        public  void Primesieve(int n) {
            prime=new boolean[n];
            for (int i = 0; i < n; i++)
                prime[i] = true;
            for (int p = 2; p * p < n; p++) {
                if (prime[p] == true) {
                    for (int i = p * p; i < n; i += p)
                        prime[i] = false;
                }
            }
        }
    }
    public Main(ThreadGroup t,Runnable r,String s,long d )
    {
        super(t,r,s,d);
    }
    public void run()
    {
        sc=new FastScanner();
        pw=new PrintWriter(System.out);
        mf=new MathF();
        solve();
        pw.flush();
        pw.close();
    }
    public static void main(String[] args)
    {
        new Main(null,null,"",1<<30).start();
    }
 
    /////////////------------------------------------/////////////
    /////////////------------------------------------/////////////
    ////////////------------------MAIN-LOGIC---------/////////////
    ////////////-------------------------------------/////////////
    ///////////--------------------------------------/////////////
 
 
 
    public void solve() {
     	int n=sc.ni();
		adj=new ArrayList[n];
		for(int i=0;i<n;i++)
		adj[i]=new ArrayList();
		visit=new int[n];
		arr=new int[n][2];
		for(int i=0;i<n-1;i++)
		{
		    int x=sc.ni();
		    int y=sc.ni();
		    x--;y--;
		   // System.out.println(x+" "+y);
		    adj[x].add(y);
		    adj[y].add(x);
		}
		Stack<Integer> stk=new Stack();
	    for(int x:adj[0])
	    {
	        stk.push(x);
	        arr[x][0]=max++;
	        //System.out.println(x+" 0     :"+arr[x][0]);
	    }
	    visit[0]=1;
	    arr[0][0]=max++;
	    while(!stk.isEmpty())
	    {
	        solve(stk.pop());
	    }
	    arr[0][1]=max++;
	    for(int i=0;i<n;i++)
	    pw.println(arr[i][0]+" "+arr[i][1]);  
    }
    public static void solve(int x)
	{
	    visit[x]=1;
	    Stack<Integer> stk=new Stack();
	    for(int k:adj[x])
	    {
	        if(visit[k]==0)
	        {stk.push(k);
	        arr[k][0]=max++;
	       // System.out.println(x+" 0     :"+arr[x][0]);
	            
	        }
	    }
	    arr[x][1]=max++;
	    //System.out.println(x+" 1     :"+arr[x][1]);
	    while(!stk.isEmpty())
	    {
	        solve(stk.pop());
	    }
	}
}