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

public class ETask {
    private static final String QUICK_ANSWER = "NO";
    private final Input in;
    private final StringBuilder out;
    private int n;
    int[] from;
    int[] to;
    private Tree tree;

    public ETask(Input in, StringBuilder out) {
        this.in = in;
        this.out = out;
    }

    public void solve() throws QuickAnswer {
        n = nextInt();
        from = new int[n];
        to = new int[n];
        tree = Tree.treeBuilder()
                .nodeCount(n)
                .build(this::nextInt);
        place(0, 1, 2);
        for (int i = 0; i < n; i++) {
            println(from[i] + " " + to[i]);
        }
    }

    int place(int node, int start, int cont) {
        from[node] = start;
        int[] children = tree.children[node];
        to[node] = cont + children.length;
        int end = cont + children.length + 1;
        for (int i = 0; i < children.length; ++i) {
            end = place(children[i], cont + children.length - 1 - i, end);
        }
        return end;
    }


    // Common functions

    private static class Input {
        private final BufferedReader in;
        private StringTokenizer tokenizer = null;

        public Input(BufferedReader in) {
            this.in = in;
        }

        String nextToken() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) tokenizer = new StringTokenizer(in.readLine());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        String nextLine() {
            try {
                return in.readLine();
            } catch (IOException e) {
                return "";
            }
        }
    }

    void quickAnswer(String answer) throws QuickAnswer {
        throw new QuickAnswer(answer);
    }

    void quickAnswer() throws QuickAnswer {
        quickAnswer(QUICK_ANSWER);
    }


    static class QuickAnswer extends Exception {
        private String answer;

        public QuickAnswer(String answer) {
            this.answer = answer;
        }
    }

    void print(Object... args) {
        String prefix = "";
        for (Object arg : args) {
            out.append(prefix);
            out.append(arg);
            prefix = " ";
        }
    }

    void println(Object... args) {
        print(args);
        out.append("\n");
    }

    void printsp(Object... args) {
        print(args);
        out.append(" ");
    }

    int nextInt() {
        return in.nextInt();
    }

    long nextLong() {
        return in.nextLong();
    }

    String nextString() {
        return in.nextLine();
    }

    int[] nextInts(int count) {
        int[] res = new int[count];
        for (int i = 0; i < count; ++i) {
            res[i] = nextInt();
        }
        return res;
    }

    int[][] nextInts(int count, int n) {
        int[][] res = new int[n][count];
        for (int i = 0; i < count; ++i) {
            for (int j = 0; j < n; j++) {
                res[j][i] = nextInt();
            }
        }
        return res;
    }

    long[] nextLongs(int count) {
        long[] res = new long[count];
        for (int i = 0; i < count; ++i) {
            res[i] = nextLong();
        }
        return res;
    }

    long[][] nextLongs(int count, int n) {
        long[][] res = new long[n][count];
        for (int i = 0; i < count; ++i) {
            for (int j = 0; j < n; j++) {
                res[j][i] = nextLong();
            }
        }
        return res;
    }

    public static void main(String[] args) {
        doMain(System.in, System.out);
    }

    static void doMain(InputStream inStream, PrintStream outStream) {
        Input in = new Input(new BufferedReader(new InputStreamReader(inStream)));
        StringBuilder totalOut = new StringBuilder();
        int count = 1;
        //count = in.nextInt();
        while (count-- > 0) {
            try {
                StringBuilder out = new StringBuilder();
                new ETask(in, out).solve();
                totalOut.append(out.toString());
            } catch (QuickAnswer e) {
                totalOut.append(e.answer);
            }
            if (count > 0) {
                totalOut.append("\n");
            }
        }
        outStream.print(totalOut.toString());
    }

    static class Graph {
        interface Input {
            int nextInt();
        }

        final int nodeCount;
        final int edgeCount;
        final int[][] neighbors;
        final int[] color;
        final int[] edgeFrom;
        final int[] edgeTo;
        final int[] edgeWeight;

        static Builder builder() {
            return new Builder();
        }

        static class Builder {
            int adjustIndex = -1;
            boolean withWeights = false;
            int nodeCount = -1;
            int edgeCount = -1;

            Builder adjustIndex(int adjustIndex) {
                this.adjustIndex = adjustIndex;
                return this;
            }

            Builder withWeights() {
                this.withWeights = true;
                return this;
            }

            Builder nodeCount(int n) {
                this.nodeCount = n;
                return this;
            }

            Builder edgeCount(int m) {
                this.edgeCount = m;
                return this;
            }

            Graph build(Input in) {
                return new Graph(
                        in,
                        nodeCount == -1 ? in.nextInt() : nodeCount,
                        edgeCount == -1 ? in.nextInt() : edgeCount,
                        adjustIndex,
                        withWeights);
            }
        }

        Graph(Input in, int nodeCount, int m, int adjustIndex, boolean withWeights) {
            this.nodeCount = nodeCount;
            this.edgeCount = m;
            this.color = new int[nodeCount];
            int[] cnt = new int[nodeCount];
            edgeFrom = new int[m];
            edgeTo = new int[m];
            edgeWeight = new int[m];
            for (int i = 0; i < m; ++i) {
                int x = in.nextInt() + adjustIndex;
                int y = in.nextInt() + adjustIndex;
                edgeFrom[i] = x;
                edgeTo[i] = y;
                edgeWeight[i] = withWeights ? in.nextInt() : 1;
                cnt[x]++;
                cnt[y]++;
            }
            this.neighbors = new int[nodeCount][];
            for (int i = 0; i < nodeCount; i++) {
                neighbors[i] = new int[cnt[i]];
            }
            for (int i = 0; i < m; ++i) {
                int from = edgeFrom[i];
                int to = edgeTo[i];
                neighbors[from][--cnt[from]] = to;
                neighbors[to][--cnt[to]] = from;
            }
        }
    }

    static class IntQueue {
        final int[] togo;
        int curr;
        int end;

        public IntQueue(int maxLen) {
            togo = new int[maxLen];
        }

        void add(int val) {
            togo[end++] = val;
        }

        int poll() {
            return togo[curr++];
        }

        boolean isEmpty() {
            return curr == end;
        }
    }

    static class Tree extends Graph {
        final int[] level;
        final int[] parent;
        final int[][] children;

        static Builder treeBuilder() {
            return new Builder();
        }

        static class Builder {
            private int rootNode = 0;
            int adjustIndex = -1;
            boolean withWeights = false;
            int nodeCount = -1;

            Builder rootNode(int rootNode) {
                this.rootNode = rootNode;
                return this;
            }

            Builder adjustIndex(int adjustIndex) {
                this.adjustIndex = adjustIndex;
                return this;
            }

            Builder withWeights() {
                this.withWeights = true;
                return this;
            }

            Builder nodeCount(int n) {
                this.nodeCount = n;
                return this;
            }


            public Tree build(Input in) {
                return new Tree(
                        in,
                        nodeCount == -1 ? in.nextInt() : nodeCount,
                        adjustIndex,
                        withWeights,
                        rootNode);
            }
        }

        Tree(Input in, int n, int adjustIndex, boolean withWeights, int rootNode) {
            super(in, n, n - 1, adjustIndex, withWeights);
            level = new int[n];
            parent = new int[n];
            children = new int[n][];

            IntQueue iq = new IntQueue(n);
            level[rootNode] = 0;
            parent[rootNode] = -1;
            iq.add(rootNode);
            while (!iq.isEmpty()) {
                int node = iq.poll();
                int childLevel = level[node] + 1;
                if (parent[node] == -1) {
                    children[node] = new int[neighbors[node].length];
                } else {
                    children[node] = new int[neighbors[node].length - 1];
                }
                int curr = 0;
                for (int neighbor : neighbors[node]) {
                    if (neighbor == parent[node]) continue;
                    level[neighbor] = childLevel;
                    parent[neighbor] = node;
                    children[node][curr++] = neighbor;
                    iq.add(neighbor);
                }
            }
        }
    }
}