Takahashi's office has N rooms. Each room has an ID from 1 to N. There are also N-1 corridors, and the i-th corridor connects Room a_i and Room b_i. It is known that we can travel between any two rooms using only these corridors.

Takahashi has got lost in one of the rooms. Let this room be r. He decides to get back to his room, Room 1, by repeatedly traveling in the following manner:

* Travel to the room with the smallest ID among the rooms that are adjacent to the rooms already visited, but not visited yet.



Let c_r be the number of travels required to get back to Room 1. Find all of c_2,c_3,...,c_N. Note that, no matter how many corridors he passes through in a travel, it still counts as one travel.

Constraints

* 2 \leq N \leq 2\times 10^5
* 1 \leq a_i,b_i \leq N
* a_i \neq b_i
* The graph given as input is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}


Output

Print c_r for each r, in the following format:


c_2 c_3 ... c_N

Output

Print c_r for each r, in the following format:


c_2 c_3 ... c_N

Examples

Input

6
1 5
5 6
6 2
6 3
6 4


Output

5 5 5 1 5


Input

6
1 2
2 3
3 4
4 5
5 6


Output

1 2 3 4 5


Input

10
1 5
5 6
6 10
6 4
10 3
10 8
8 2
4 7
4 9


Output

7 5 3 1 3 4 7 4 5
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            EWanderingTKHS solver = new EWanderingTKHS();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class EWanderingTKHS {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            Node[] nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new Node();
                nodes[i].id = i;
                nodes[i].lctNode = new LCTNode();
                nodes[i].lctNode.id = i;
                nodes[i].lctNode.pushUp();
            }
            for (int i = 0; i < n - 1; i++) {
                Node a = nodes[in.readInt() - 1];
                Node b = nodes[in.readInt() - 1];
                a.adj.add(b);
                b.adj.add(a);

                LCTNode.join(a.lctNode, b.lctNode);
            }

            for (Node node : nodes[0].adj) {
                dfs(node, nodes[0], nodes[0], node, nodes[0]);
            }
            solve(nodes[0], null, 0);

            for (int i = 1; i < n; i++) {
                out.println(nodes[i].cnt);
            }
        }

        public int maxIdBetween(Node a, Node b) {
            LCTNode.findRoute(a.lctNode, b.lctNode);
            LCTNode.splay(a.lctNode);
            return a.lctNode.maxId;
        }

        public void dfs(Node root, Node p, Node max, Node second, Node top) {
            root.p = p;
            if (max.id <= root.id) {
                root.add++;
            } else if (max.p != null && maxIdBetween(max.p, top) >=
                    maxIdBetween(root, second)) {
                max.add++;
            } else {
                second.add++;
            }

            for (Node node : root.adj) {
                if (node == p) {
                    continue;
                }
                if (max.id > root.id) {
                    dfs(node, root, max, second, top);
                } else {
                    dfs(node, root, root, node, top);
                }
            }
        }

        public void solve(Node root, Node p, int cnt) {
            cnt += root.add;
            root.cnt = cnt;
            for (Node node : root.adj) {
                if (node == p) {
                    continue;
                }
                solve(node, root, cnt);
            }
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class Node {
        List<Node> adj = new ArrayList<>();
        int id;
        int cnt;
        int add;
        Node p;
        LCTNode lctNode;

        public String toString() {
            return String.format("%d=%d", id, add);
        }

    }

    static class LCTNode {
        public static final LCTNode NIL = new LCTNode();
        LCTNode left = NIL;
        LCTNode right = NIL;
        LCTNode father = NIL;
        LCTNode treeFather = NIL;
        boolean reverse;
        int id;
        int maxId;

        static {
            NIL.left = NIL;
            NIL.right = NIL;
            NIL.father = NIL;
            NIL.treeFather = NIL;
            NIL.maxId = NIL.id = -1;
        }

        public static void access(LCTNode x) {
            LCTNode last = NIL;
            while (x != NIL) {
                splay(x);
                x.right.father = NIL;
                x.right.treeFather = x;
                x.setRight(last);
                x.pushUp();

                last = x;
                x = x.treeFather;
            }
        }

        public static void makeRoot(LCTNode x) {
            access(x);
            splay(x);
            x.reverse();
        }

        public static void join(LCTNode y, LCTNode x) {
            makeRoot(x);
            x.treeFather = y;
        }

        public static void findRoute(LCTNode x, LCTNode y) {
            makeRoot(y);
            access(x);
        }

        public static void splay(LCTNode x) {
            if (x == NIL) {
                return;
            }
            LCTNode y, z;
            while ((y = x.father) != NIL) {
                if ((z = y.father) == NIL) {
                    y.pushDown();
                    x.pushDown();
                    if (x == y.left) {
                        zig(x);
                    } else {
                        zag(x);
                    }
                } else {
                    z.pushDown();
                    y.pushDown();
                    x.pushDown();
                    if (x == y.left) {
                        if (y == z.left) {
                            zig(y);
                            zig(x);
                        } else {
                            zig(x);
                            zag(x);
                        }
                    } else {
                        if (y == z.left) {
                            zag(x);
                            zig(x);
                        } else {
                            zag(y);
                            zag(x);
                        }
                    }
                }
            }

            x.pushDown();
            x.pushUp();
        }

        public static void zig(LCTNode x) {
            LCTNode y = x.father;
            LCTNode z = y.father;
            LCTNode b = x.right;

            y.setLeft(b);
            x.setRight(y);
            z.changeChild(y, x);

            y.pushUp();
        }

        public static void zag(LCTNode x) {
            LCTNode y = x.father;
            LCTNode z = y.father;
            LCTNode b = x.left;

            y.setRight(b);
            x.setLeft(y);
            z.changeChild(y, x);

            y.pushUp();
        }

        public String toString() {
            return "" + id;
        }

        public void pushDown() {
            if (this == NIL) {
                return;
            }
            if (reverse) {
                reverse = false;

                LCTNode tmpNode = left;
                left = right;
                right = tmpNode;

                left.reverse();
                right.reverse();
            }

            left.treeFather = treeFather;
            right.treeFather = treeFather;
        }

        public void reverse() {
            reverse = !reverse;
        }

        public void setLeft(LCTNode x) {
            left = x;
            x.father = this;
        }

        public void setRight(LCTNode x) {
            right = x;
            x.father = this;
        }

        public void changeChild(LCTNode y, LCTNode x) {
            if (left == y) {
                setLeft(x);
            } else {
                setRight(x);
            }
        }

        public void pushUp() {
            if (this == NIL) {
                return;
            }
            maxId = Math.max(left.maxId, right.maxId);
            maxId = Math.max(id, maxId);
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }
}

