Given a rooted tree with n nodes. The Night King removes exactly one node from the tree and all the edges associated with it. Doing this splits the tree and forms a forest. The node which is removed is not a part of the forest.

The root of a tree in the forest is the node in that tree which does not have a parent. We define the strength of the forest as the size of largest tree in forest.

Jon Snow wants to minimize the strength of the forest. To do this he can perform the following operation at most once.

He removes the edge between a node and its parent and inserts a new edge between this node and any other node in forest such that the total number of trees in forest remain same.

For each node v you need to find the minimum value of strength of the forest formed when node v is removed.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 105) — the number of vertices in the tree. Each of the next n lines contains a pair of vertex indices ui and vi (1 ≤ ui, vi ≤ n) where ui is the parent of vi. If ui = 0 then vi is the root.

Output

Print n line each containing a single integer. The i-th of them should be equal to minimum value of strength of forest formed when i-th node is removed and Jon Snow performs the operation described above at most once.

Examples

Input

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


Output

3
4
5
5
5
9
9
9
9
9


Input

2
2 1
0 2


Output

1
1

Note

The tree for first test case is depicted below. <image> When you remove the first node, the tree splits to form the following forest. The strength of this forest is 4. <image> Jon Snow now changes the parent of vertex 10 from 5 to 3. The strength of forest now becomes 3. <image>
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.TreeMap;
import java.util.Map;
import java.util.Map.Entry;
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) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskG solver = new TaskG();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskG {
        int n;
        Graph graph;
        int[] hardTo;
        int[] sizeSubTree;
        int[] answer;
        TreeCounter<Integer> upTree;
        TreeCounter<Integer> stack;
        TreeCounter<Integer>[] ret;

        int max(int a, int b, int c) {
            return Math.max(Math.max(a, b), c);
        }

        private void init(int v) {
            sizeSubTree[v] = 1;
            hardTo[v] = -1;
            for (int i = graph.firstOutbound(v); i != -1; i = graph.nextOutbound(i)) {
                int to = graph.destination(i);
                init(to);
                sizeSubTree[v] += sizeSubTree[to];
                if (hardTo[v] == -1 || sizeSubTree[hardTo[v]] < sizeSubTree[to]) {
                    hardTo[v] = to;
                }
            }
        }

        private void addSubTreeToUpTree(int v, int delta) {
            upTree.add(sizeSubTree[v], delta);
            for (int i = graph.firstOutbound(v); i != -1; i = graph.nextOutbound(i)) {
                int to = graph.destination(i);
                addSubTreeToUpTree(to, delta);
            }
        }

        private void dfs(int v) {
            int maxSubTree0 = Integer.MIN_VALUE;
            int maxSubTree1 = Integer.MIN_VALUE;
            int minSubTree = Integer.MAX_VALUE;
            int cntTrees = 0;
            {
                int sizeUp = n - 1;
                for (int i = graph.firstOutbound(v); i != -1; i = graph.nextOutbound(i)) {
                    int to = graph.destination(i);
                    sizeUp -= sizeSubTree[to];
                    if (maxSubTree0 < sizeSubTree[to]) {
                        maxSubTree1 = maxSubTree0;
                        maxSubTree0 = sizeSubTree[to];
                    } else if (maxSubTree1 < sizeSubTree[to]) {
                        maxSubTree1 = sizeSubTree[to];
                    }
                    minSubTree = Math.min(minSubTree, sizeSubTree[to]);
                    ++cntTrees;
                }
                if (maxSubTree0 < sizeUp) {
                    maxSubTree1 = maxSubTree0;
                    maxSubTree0 = sizeUp;
                } else if (maxSubTree1 < sizeUp) {
                    maxSubTree1 = sizeUp;
                }
                if (sizeUp != 0) {
                    minSubTree = Math.min(minSubTree, sizeUp);
                    ++cntTrees;
                }

                answer[v] = maxSubTree0;
                if (2 <= cntTrees && maxSubTree0 == sizeUp) {
                    answer[v] = Math.min(answer[v], Math.min(
                            getAnswer(upTree, 0, maxSubTree0, maxSubTree1, minSubTree),
                            getAnswer(stack, sizeSubTree[v], maxSubTree0, maxSubTree1, minSubTree)
                    ));
                }
            }

            //-------------------

            stack.add(sizeSubTree[v], 1);

            if (hardTo[v] != -1) {
                for (int i = graph.firstOutbound(v); i != -1; i = graph.nextOutbound(i)) {
                    int to = graph.destination(i);
                    if (to == hardTo[v]) {
                        continue;
                    }
                    addSubTreeToUpTree(to, 1);
                }

                dfs(hardTo[v]);
                ret[v] = ret[hardTo[v]];
                if (2 <= cntTrees && maxSubTree0 == sizeSubTree[hardTo[v]]) {
                    answer[v] = Math.min(answer[v], getAnswer(ret[v], 0, maxSubTree0, maxSubTree1, minSubTree));
                }
            } else {
                ret[v] = new TreeCounter<>();
            }
            ret[v].add(sizeSubTree[v], 1);


            for (int i = graph.firstOutbound(v); i != -1; i = graph.nextOutbound(i)) {
                int to = graph.destination(i);
                if (to == hardTo[v]) {
                    continue;
                }
                addSubTreeToUpTree(to, -1);
                dfs(to);

                // добавляешь в upTree в конце DFS
                for (Map.Entry<Integer, Integer> entry : ret[to].entrySet()) {
                    ret[v].add(entry.getKey(), entry.getValue());
                }
            }

            stack.add(sizeSubTree[v], -1);
            upTree.add(sizeSubTree[v], 1);
        }

        private int getAnswer(TreeCounter<Integer> counter, int delta, int maxSubTree0, int maxSubTree1,
                              int minSubTree) {
            int ans = Integer.MAX_VALUE;

            for (int addd = 0; addd <= 1; addd++) {
                int target = (maxSubTree0 - minSubTree + addd) >> 1;
                Map.Entry<Integer, Integer> entry;

                entry = counter.floorEntry(target + delta);
                if (entry != null) {
                    int sub = entry.getKey() - delta;
                    ans = Math.min(ans, max(maxSubTree1, maxSubTree0 - sub, minSubTree + sub));
                }

                entry = counter.ceilingEntry(target + delta);
                if (entry != null) {
                    int sub = entry.getKey() - delta;
                    ans = Math.min(ans, max(maxSubTree1, maxSubTree0 - sub, minSubTree + sub));
                }
            }
            return ans;
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            //
            n = in.readInt();
            graph = new Graph(n, n - 1);
            int root = -1;
            for (int iter = 0; iter < n; iter++) {
                int u = in.readInt() - 1;
                int v = in.readInt() - 1;
                if (u == -1) {
                    root = v;
                } else {
                    graph.addSimpleEdge(u, v);
//                out.printLine(u, v);
                }
            }
        /**/

        /*/
        n = (int) 1e5;
        graph = new Graph(n, n - 1);
        int root = 0;
        for (int v = 2; v <= n; v++) {
            int p = v / 2;
            graph.addSimpleEdge(p - 1, v - 1);
        }
        /**/


            hardTo = new int[n];
            sizeSubTree = new int[n];
            init(root);

            answer = new int[n];
            Arrays.fill(answer, Integer.MAX_VALUE);
            upTree = new TreeCounter<>();
            stack = new TreeCounter<>();
            ret = new TreeCounter[n];
            dfs(root);

            for (int x : answer) {
                out.printLine(x);
            }


            long cnt = 0;
            for (int x : upTree.values()) {
                cnt += x;
            }
            if (cnt != n) {
                throw new RuntimeException();
            }

            cnt = 0;
            for (Integer x : ret[root].values()) {
                cnt += x;
            }
            if (cnt != n) {
                throw new RuntimeException();
            }
        }

    }

    static class TreeCounter<K> extends TreeMap<K, Integer> {
        public TreeCounter() {
            super();
        }

        public void add(K key, int delta) {
            int cnt = get(key) + delta;
            put(key, cnt);
            if (cnt == 0) {
                remove(key);
            }
        }


        public Integer get(Object key) {
            if (containsKey(key)) {
                return super.get(key);
            }
            return 0;
        }

    }

    static interface Edge {
    }

    static class Graph {
        public static final int REMOVED_BIT = 0;
        protected int vertexCount;
        protected int edgeCount;
        private int[] firstOutbound;
        private int[] firstInbound;
        private Edge[] edges;
        private int[] nextInbound;
        private int[] nextOutbound;
        private int[] from;
        private int[] to;
        private long[] weight;
        public long[] capacity;
        private int[] reverseEdge;
        private int[] flags;

        public Graph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public Graph(int vertexCount, int edgeCapacity) {
            this.vertexCount = vertexCount;
            firstOutbound = new int[vertexCount];
            Arrays.fill(firstOutbound, -1);

            from = new int[edgeCapacity];
            to = new int[edgeCapacity];
            nextOutbound = new int[edgeCapacity];
            flags = new int[edgeCapacity];
        }

        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            ensureEdgeCapacity(edgeCount + 1);
            if (firstOutbound[fromID] != -1) {
                nextOutbound[edgeCount] = firstOutbound[fromID];
            } else {
                nextOutbound[edgeCount] = -1;
            }
            firstOutbound[fromID] = edgeCount;
            if (firstInbound != null) {
                if (firstInbound[toID] != -1) {
                    nextInbound[edgeCount] = firstInbound[toID];
                } else {
                    nextInbound[edgeCount] = -1;
                }
                firstInbound[toID] = edgeCount;
            }
            this.from[edgeCount] = fromID;
            this.to[edgeCount] = toID;
            if (capacity != 0) {
                if (this.capacity == null) {
                    this.capacity = new long[from.length];
                }
                this.capacity[edgeCount] = capacity;
            }
            if (weight != 0) {
                if (this.weight == null) {
                    this.weight = new long[from.length];
                }
                this.weight[edgeCount] = weight;
            }
            if (reverseEdge != -1) {
                if (this.reverseEdge == null) {
                    this.reverseEdge = new int[from.length];
                    Arrays.fill(this.reverseEdge, 0, edgeCount, -1);
                }
                this.reverseEdge[edgeCount] = reverseEdge;
            }
            if (edges != null) {
                edges[edgeCount] = createEdge(edgeCount);
            }
            return edgeCount++;
        }

        protected final GraphEdge createEdge(int id) {
            return new GraphEdge(id);
        }

        public final int addFlowWeightedEdge(int from, int to, long weight, long capacity) {
            if (capacity == 0) {
                return addEdge(from, to, weight, 0, -1);
            } else {
                int lastEdgeCount = edgeCount;
                addEdge(to, from, -weight, 0, lastEdgeCount + entriesPerEdge());
                return addEdge(from, to, weight, capacity, lastEdgeCount);
            }
        }

        protected int entriesPerEdge() {
            return 1;
        }

        public final int addWeightedEdge(int from, int to, long weight) {
            return addFlowWeightedEdge(from, to, weight, 0);
        }

        public final int addSimpleEdge(int from, int to) {
            return addWeightedEdge(from, to, 0);
        }

        public final int firstOutbound(int vertex) {
            int id = firstOutbound[vertex];
            while (id != -1 && isRemoved(id)) {
                id = nextOutbound[id];
            }
            return id;
        }

        public final int nextOutbound(int id) {
            id = nextOutbound[id];
            while (id != -1 && isRemoved(id)) {
                id = nextOutbound[id];
            }
            return id;
        }

        public final int destination(int id) {
            return to[id];
        }

        public final boolean flag(int id, int bit) {
            return (flags[id] >> bit & 1) != 0;
        }

        public final boolean isRemoved(int id) {
            return flag(id, REMOVED_BIT);
        }

        protected void ensureEdgeCapacity(int size) {
            if (from.length < size) {
                int newSize = Math.max(size, 2 * from.length);
                if (edges != null) {
                    edges = resize(edges, newSize);
                }
                from = resize(from, newSize);
                to = resize(to, newSize);
                nextOutbound = resize(nextOutbound, newSize);
                if (nextInbound != null) {
                    nextInbound = resize(nextInbound, newSize);
                }
                if (weight != null) {
                    weight = resize(weight, newSize);
                }
                if (capacity != null) {
                    capacity = resize(capacity, newSize);
                }
                if (reverseEdge != null) {
                    reverseEdge = resize(reverseEdge, newSize);
                }
                flags = resize(flags, newSize);
            }
        }

        protected final int[] resize(int[] array, int size) {
            int[] newArray = new int[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private long[] resize(long[] array, int size) {
            long[] newArray = new long[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private Edge[] resize(Edge[] array, int size) {
            Edge[] newArray = new Edge[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        protected class GraphEdge implements Edge {
            protected int id;

            protected GraphEdge(int id) {
                this.id = id;
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(int i) {
            writer.println(i);
        }

    }
}

