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.util.Arrays;
import java.util.Random;
import java.util.ArrayList;
import java.util.Map;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.List;
import java.util.AbstractMap;
import java.util.TreeMap;
import java.io.Closeable;
import java.io.Writer;
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);
            GTheWindsOfWinter solver = new GTheWindsOfWinter();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class GTheWindsOfWinter {
        int n;
        TreeMap<Integer, Integer> top = new TreeMap<>();
        TreeMap<Integer, Integer> stack = new TreeMap<>();
        TreeMap<Integer, Integer> bot = new TreeMap<>();
        IntegerArrayList sizeList = new IntegerArrayList((int) 1e5);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            n = in.readInt();

            Node[] nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new Node();
                nodes[i].id = i;
            }

            Node root = null;
            for (int i = 0; i < n; i++) {
                int pId = in.readInt() - 1;
                Node b = nodes[in.readInt() - 1];
                if (pId == -1) {
                    root = b;
                    continue;
                }
                Node a = nodes[pId];
                a.adj.add(b);
                b.adj.add(a);
            }

            if (n == 1) {
                out.println(0);
                return;
            }


            assert root != null;
            dfsForSize(root, null);
            for (Node node : nodes) {
                add(top, node.size);
            }

            dfsForSolve(root, null, false);

            for (Node node : nodes) {
                out.println(node.ans);
            }
        }

        public void add(TreeMap<Integer, Integer> map, int x) {
            int cnt = map.getOrDefault(x, 0) + 1;
            map.put(x, cnt);
        }

        public void delete(TreeMap<Integer, Integer> map, int x) {
            int cnt = map.getOrDefault(x, 0) - 1;
            if (cnt == 0) {
                map.remove(x);
            } else {
                map.put(x, cnt);
            }
        }

        public void dfsForSize(Node root, Node p) {
            root.size = 1;
            for (Node node : root.adj) {
                if (node == p) {
                    continue;
                }
                dfsForSize(node, root);
                root.size += node.size;
                if (root.heavy == null || root.heavy.size < node.size) {
                    root.heavy = node;
                }
            }
        }

        public void dfsForUndo(Node root, Node p) {
            delete(bot, root.size);
            add(top, root.size);
            for (Node node : root.adj) {
                if (node == p) {
                    continue;
                }
                dfsForUndo(node, root);
            }
        }

        public void dfsForDo(Node root, Node p) {
            add(bot, root.size);
            delete(top, root.size);
            for (Node node : root.adj) {
                if (node == p) {
                    continue;
                }
                dfsForDo(node, root);
            }
        }

        public int optimal(TreeMap<Integer, Integer> structure, TreeMap<Integer, Integer> extra, int rootSize) {
            if (sizeList.size() == 1) {
                return sizeList.tail();
            }
            int secondMax = sizeList.get(sizeList.size() - 2);
            int max = sizeList.tail();
            int min = sizeList.first();
            //\min(min+d, max-d),

            int half = (max - min) / 2;
            Integer floor = structure.floorKey(half);
            Integer ceil = structure.ceilingKey(half);

            int ans = max;
            if (floor != null) {
                ans = Math.min(ans, Math.max(Math.max(max - floor, min + floor), secondMax));
            }
            if (ceil != null && ceil != max) {
                ans = Math.min(ans, Math.max(Math.max(max - ceil, min + ceil), secondMax));
            }

            if (extra != null) {
                floor = extra.floorKey(half + rootSize);
                ceil = extra.ceilingKey(half + rootSize);

                if (floor != null) {
                    floor -= rootSize;
                    ans = Math.min(ans, Math.max(Math.max(max - floor, min + floor), secondMax));
                }
                if (ceil != null && ceil != max) {
                    ceil -= rootSize;
                    ans = Math.min(ans, Math.max(Math.max(max - ceil, min + ceil), secondMax));
                }
            }
            return ans;
        }

        public void dfsForSolve(Node root, Node p, boolean undo) {
            delete(top, root.size);
            add(stack, root.size);

            for (Node node : root.adj) {
                if (node == p || node == root.heavy) {
                    continue;
                }
                dfsForSolve(node, root, true);
                assert bot.isEmpty();
            }

            if (root.heavy != null) {
                dfsForSolve(root.heavy, root, false);
            }

            add(top, root.size);
            delete(stack, root.size);

            sizeList.clear();
            for (Node node : root.adj) {
                if (node == p) {
                    sizeList.add(n - root.size);
                } else {
                    sizeList.add(node.size);
                }
            }
            sizeList.sort();

            root.ans = sizeList.tail();
            if (root.heavy != null && root.heavy.size == sizeList.tail()) {
                root.ans = Math.min(root.ans, optimal(bot, null, root.size));
            }

            for (Node node : root.adj) {
                if (node == p || node == root.heavy) {
                    continue;
                }
                dfsForDo(node, root);
            }
            add(bot, root.size);
            delete(top, root.size);

            if (n - root.size == sizeList.tail()) {
                root.ans = Math.min(root.ans, optimal(top, stack, root.size));
            }

            if (undo) {
                dfsForUndo(root, p);
            }
        }

    }

    static class Randomized {
        public static void shuffle(int[] data, int from, int to) {
            to--;
            for (int i = from; i <= to; i++) {
                int s = nextInt(i, to);
                int tmp = data[i];
                data[i] = data[s];
                data[s] = tmp;
            }
        }

        public static int nextInt(int l, int r) {
            return RandomWrapper.INSTANCE.nextInt(l, r);
        }

    }

    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 SequenceUtils {
        public static boolean equal(int[] a, int al, int ar, int[] b, int bl, int br) {
            if ((ar - al) != (br - bl)) {
                return false;
            }
            for (int i = al, j = bl; i <= ar; i++, j++) {
                if (a[i] != b[j]) {
                    return false;
                }
            }
            return true;
        }

    }

    static class RandomWrapper {
        private Random random;
        public static final RandomWrapper INSTANCE = new RandomWrapper(new Random());

        public RandomWrapper() {
            this(new Random());
        }

        public RandomWrapper(Random random) {
            this.random = random;
        }

        public int nextInt(int l, int r) {
            return random.nextInt(r - l + 1) + l;
        }

    }

    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;
        }

    }

    static class Node {
        List<Node> adj = new ArrayList<>();
        int size;
        Node heavy;
        int ans;
        int id;

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

    }

    static class IntegerArrayList implements Cloneable {
        private int size;
        private int cap;
        private int[] data;
        private static final int[] EMPTY = new int[0];

        public IntegerArrayList(int cap) {
            this.cap = cap;
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
        }

        public IntegerArrayList(IntegerArrayList list) {
            this.size = list.size;
            this.cap = list.cap;
            this.data = Arrays.copyOf(list.data, size);
        }

        public IntegerArrayList() {
            this(0);
        }

        public void ensureSpace(int req) {
            if (req > cap) {
                while (cap < req) {
                    cap = Math.max(cap + 10, 2 * cap);
                }
                data = Arrays.copyOf(data, cap);
            }
        }

        private void checkRange(int i) {
            if (i < 0 || i >= size) {
                throw new ArrayIndexOutOfBoundsException();
            }
        }

        public int get(int i) {
            checkRange(i);
            return data[i];
        }

        public void add(int x) {
            ensureSpace(size + 1);
            data[size++] = x;
        }

        public void addAll(int[] x, int offset, int len) {
            ensureSpace(size + len);
            System.arraycopy(x, offset, data, size, len);
            size += len;
        }

        public void addAll(IntegerArrayList list) {
            addAll(list.data, 0, list.size);
        }

        public void sort() {
            if (size <= 1) {
                return;
            }
            Randomized.shuffle(data, 0, size);
            Arrays.sort(data, 0, size);
        }

        public int first() {
            checkRange(0);
            return data[0];
        }

        public int tail() {
            checkRange(0);
            return data[size - 1];
        }

        public int size() {
            return size;
        }

        public int[] toArray() {
            return Arrays.copyOf(data, size);
        }

        public void clear() {
            size = 0;
        }

        public String toString() {
            return Arrays.toString(toArray());
        }

        public boolean equals(Object obj) {
            if (!(obj instanceof IntegerArrayList)) {
                return false;
            }
            IntegerArrayList other = (IntegerArrayList) obj;
            return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1);
        }

        public int hashCode() {
            int h = 1;
            for (int i = 0; i < size; i++) {
                h = h * 31 + Integer.hashCode(data[i]);
            }
            return h;
        }

        public IntegerArrayList clone() {
            IntegerArrayList ans = new IntegerArrayList();
            ans.addAll(this);
            return ans;
        }

    }
}

