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>
#include <bits/stdc++.h>
using namespace std;
const int INF = 1791791791;
const long long INFLL = 1791791791791791791ll;
template <int input_buf_size, int output_buf_size>
class FastIO {
  char cbuf[input_buf_size + 1];
  int icur = 0;
  inline bool go_to_next_token() {
    while (cbuf[icur] == ' ' || cbuf[icur] == '\n') icur++;
    while (cbuf[icur] == 0) {
      icur = 0;
      if (fgets(cbuf, sizeof(cbuf), stdin) != cbuf) return false;
      while (cbuf[icur] == ' ' || cbuf[icur] == '\n') icur++;
    }
    return true;
  }

 public:
  string readString() {
    assert(go_to_next_token());
    string ans;
    while (cbuf[icur] != ' ' && cbuf[icur] != '\n' && cbuf[icur] != 0)
      ans.push_back(cbuf[icur++]);
    ans.shrink_to_fit();
    return ans;
  }
  template <class int_type>
  int_type readInt() {
    assert(go_to_next_token());
    int_type x = 0;
    bool m = cbuf[icur] == '-';
    if (m) icur++;
    while ('0' <= cbuf[icur] && cbuf[icur] <= '9') {
      x *= 10;
      x += (cbuf[icur] - '0');
      icur++;
    }
    if (m) x = -x;
    return x;
  }
  bool seekEof() { return !go_to_next_token(); }

 private:
  char obuf[output_buf_size + 1];
  int ocur = 0;
  inline void write_string(const char* str, size_t sz = 0) {
    if (sz == 0) sz = strlen(str);
    if (ocur + sz > output_buf_size) {
      fputs(obuf, stdout);
      fputs(str, stdout);
      ocur = 0;
      obuf[0] = 0;
      return;
    }
    strcpy(obuf + ocur, str);
    ocur += sz;
    obuf[ocur] = 0;
  }

 public:
  template <class int_type>
  void writeInt(int_type x, bool sp = true) {
    char buf[20];
    int c = 0;
    if (x < 0) {
      buf[c++] = '-';
      x = -x;
    }
    int s = c;
    if (x == 0) {
      buf[c++] = '0';
    }
    while (x > 0) {
      buf[c++] = (x % 10) + '0';
      x /= 10;
    }
    for (int i = 0; 2 * i < c - s; i++) {
      swap(buf[s + i], buf[c - 1 - i]);
    }
    buf[c] = 0;
    write_string(buf, c);
    if (sp) write_string(" ", 1);
  }
  void writeString(string s, bool space = true) {
    write_string(s.c_str(), s.size());
    if (space) write_string(" ", 1);
  }
  void writeEndl() { write_string("\n", 1); }
  void flush() {
    fputs(obuf, stdout);
    ocur = 0;
    obuf[0] = 0;
  }

 private:
  bool lflush;

 public:
  FastIO(bool local_flush) {
    obuf[0] = 0;
    lflush = local_flush;
  }
  ~FastIO() { fputs(obuf, stdout); }
};
FastIO<10000000, 10000000> IO(true);
template <class T>
class my_multiset {
  map<T, int> make_pair;
  int s = 0;

 public:
  my_multiset() {}
  void insert(T x) {
    make_pair[x]++;
    s++;
  }
  void erase(T x) {
    auto it = make_pair.find(x);
    it->second--;
    if (it->second == 0) make_pair.erase(it);
    s--;
  }
  size_t size() const { return s; }
  void clear() { *this = my_multiset<T>(); }
  T any() { return make_pair.begin()->first; }
  map<T, int>& access() { return make_pair; }
  int count(T x) {
    if (make_pair.count(x)) return make_pair[x];
    return 0;
  }
};
class segment_tree {
  int n;
  vector<my_multiset<int> > t;
  int update(int v, int L, int R, int i, int x) {
    if (R <= i || i < L)
      return -INF;
    else if (L == R - 1) {
      int ret = -INF;
      if (t[v].size()) ret = t[v].any();
      t[v].clear();
      t[v].insert(x);
      return ret;
    } else {
      int rem = -INF;
      rem = max(rem, update(2 * v + 1, L, (L + R) >> 1, i, x));
      rem = max(rem, update(2 * v + 2, (L + R) >> 1, R, i, x));
      if (rem != -INF && t[v].count(rem)) t[v].erase(rem);
      t[v].insert(x);
      return rem;
    }
  }
  int min_in_segment(int v, int L, int R, int l, int r, int a, int b) {
    if (R <= l || r <= L)
      return INF;
    else if (l <= L && R <= r) {
      auto it = t[v].access().lower_bound(a);
      return (it != t[v].access().end() && it->first < b ? it->first : INF);
    } else
      return min(min_in_segment(2 * v + 1, L, (L + R) >> 1, l, r, a, b),
                 min_in_segment(2 * v + 2, (L + R) >> 1, R, l, r, a, b));
  }
  int max_in_segment(int v, int L, int R, int l, int r, int a, int b) {
    if (R <= l || r <= L)
      return -INF;
    else if (l <= L && R <= r) {
      auto it = t[v].access().lower_bound(b);
      if (it != t[v].access().begin())
        return (prev(it)->first >= a ? prev(it)->first : -INF);
      else
        return -INF;
    } else
      return max(max_in_segment(2 * v + 1, L, (L + R) >> 1, l, r, a, b),
                 max_in_segment(2 * v + 2, (L + R) >> 1, R, l, r, a, b));
  }
  int erase(int v, int L, int R, int i) {
    if (L > i || R <= i)
      return -INF;
    else if (L == R - 1) {
      int ret = -INF;
      if (t[v].size()) ret = t[v].access().begin()->first;
      t[v].clear();
      return ret;
    } else {
      int rem = max(erase(2 * v + 1, L, (L + R) >> 1, i),
                    erase(2 * v + 2, (L + R) >> 1, R, i));
      if (rem != -INF) t[v].erase(rem);
      return rem;
    }
  }

 public:
  segment_tree(int _n) {
    n = _n;
    t.resize(4 * n);
  }
  void update(int i, int x) { update(0, 0, n, i, x); }
  int min_in_segment(int l, int r, int a, int b) {
    if (l >= r) return INF;
    return min_in_segment(0, 0, n, l, r, a, b);
  }
  int max_in_segment(int l, int r, int a, int b) {
    if (l >= r) return -INF;
    return max_in_segment(0, 0, n, l, r, a, b);
  }
  void erase(int i) { erase(0, 0, n, i); }
};
class basic_tree {
 protected:
  int n;
  vector<vector<int> > tree;

 public:
  basic_tree(int _n = 0) {
    n = _n;
    tree.resize(n);
  }
  size_t size() const { return n; }
  void add_vertex() {
    n++;
    tree.push_back(vector<int>());
  }
  virtual void add_edge(int u, int v) {
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  virtual void process() {}
};
class euler_tour_builder : public basic_tree {
  int ct = 0;
  vector<int> _tin, _tout;
  vector<int> euler;
  void tdfs(int v, int par) {
    _tin[v] = ct++;
    euler.push_back(v);
    for (int u : tree[v]) {
      if (u != par) {
        tdfs(u, v);
      }
    }
    _tout[v] = ct;
  }

 protected:
  int rt;

 public:
  euler_tour_builder(int _n = 0) : basic_tree(_n) {}
  virtual void process() {
    _tin.resize(n);
    _tout.resize(n);
    tdfs(rt, -1);
  }
  bool is_ancestor(int u, int v) {
    return tin(u) <= tin(v) && tin(v) < tout(u);
  }
  virtual void set_root(int v) { rt = v; }
  inline const int& tin(int v) const { return _tin[v]; }
  inline const int& tout(int v) const { return _tout[v]; }
  int operator[](const int& i) const { return euler[i]; }
};
class subtree_size_builder : public basic_tree {
 protected:
  vector<int> sz;
  int rt;

 private:
  void dfs(int v, int par) {
    sz[v] = 1;
    for (int u : tree[v])
      if (u != par) {
        dfs(u, v);
        sz[v] += sz[u];
      }
  }

 public:
  subtree_size_builder(int _n = 0) : basic_tree(_n) {}
  virtual void process() {
    sz.resize(n);
    dfs(rt, -1);
  }
  virtual void set_root(int v) { rt = v; }
  int subtree_size(int v) const { return sz[v]; }
};
class prob_G : public euler_tour_builder, public subtree_size_builder {
  int& n;
  vector<vector<int> >& tree;
  int& rt;
  segment_tree cur;
  segment_tree parents;
  vector<int> csz;
  int min_in_subtree(int root, int v, int a, int b, int x) {
    if (is_ancestor(root, v))
      return min(cur.min_in_segment(tin(v) + 1, tout(v), a, b),
                 parents.min_in_segment(tin(v) + 1, tout(v), a - x, b - x) + x);
    else if (tin(v) == 0)
      return min(min(cur.min_in_segment(1, tin(root), a, b),
                     cur.min_in_segment(tout(root), n, a, b)),
                 min(parents.min_in_segment(1, tin(root), a - x, b - x) + x,
                     parents.min_in_segment(tout(root), n, a - x, b - x) + x));
    else {
      return min(min(cur.min_in_segment(0, tin(root), a, b),
                     cur.min_in_segment(tout(root), n, a, b)),
                 min(parents.min_in_segment(0, tin(root), a - x, b - x) + x,
                     parents.min_in_segment(tout(root), n, a - x, b - x) + x));
    }
  }
  int max_in_subtree(int root, int v, int a, int b, int x) {
    if (is_ancestor(root, v))
      return max(cur.max_in_segment(tin(v) + 1, tout(v), a, b),
                 parents.max_in_segment(tin(v) + 1, tout(v), a - x, b - x) + x);
    else if (tin(v) == 0)
      return max(max(cur.max_in_segment(1, tin(root), a, b),
                     cur.max_in_segment(tout(root), n, a, b)),
                 max(parents.max_in_segment(1, tin(root), a - x, b - x) + x,
                     parents.max_in_segment(tout(root), n, a - x, b - x) + x));
    else
      return max(max(cur.max_in_segment(0, tin(root), a, b),
                     cur.max_in_segment(tout(root), n, a, b)),
                 max(parents.max_in_segment(0, tin(root), a - x, b - x) + x,
                     parents.max_in_segment(tout(root), n, a - x, b - x) + x));
  }
  int gsz(int v) { return csz[tin(v)]; }
  vector<int> st;
  void dfs(int v, int par) {
    st.push_back(v);
    cur.erase(tin(v));
    parents.update(tin(v), sz[v]);
    for (int u : tree[v]) {
      if (u != par) {
        csz[tin(v)] = n - sz[u];
        dfs(u, v);
        csz[tin(v)] = sz[v];
      }
    }
    st.pop_back();
    cur.update(tin(v), sz[v]);
    parents.erase(tin(v));
    vector<int> children = tree[v];
    sort((children).begin(), (children).end(),
         [this](const int& i, const int& j) -> bool {
           return csz[tin(i)] < csz[tin(j)];
         });
    if (children.empty())
      ans[v] = 0;
    else if (children.size() == 1 ||
             gsz(children.back()) == gsz(children[children.size() - 2])) {
      ans[v] = gsz(children.back());
    } else {
      int midl = (gsz(children.back()) + gsz(children[0])) / 2;
      int midr = (gsz(children.back()) + gsz(children[0]) + 1) / 2;
      int x;
      ans[v] = gsz(children.back());
      if ((x = min_in_subtree(v, children.back(), gsz(children.back()) - midr,
                              INF, -sz[v])) != INF) {
        ans[v] = min(ans[v], max(gsz(children[0]) + x,
                                 max(gsz(children.back()) - x,
                                     gsz(children[children.size() - 2]))));
      }
      if (abs(gsz(children[0]) + x - (gsz(children.back()) - x)) <= 1) return;
      if ((x = max_in_subtree(v, children.back(), -INF,
                              gsz(children.back()) - midl, -sz[v])) != -INF) {
        ans[v] = min(ans[v], max(gsz(children[0]) + x,
                                 max(gsz(children.back()) - x,
                                     gsz(children[children.size() - 2]))));
      }
    }
  }

 public:
  prob_G(int _n = 0)
      : euler_tour_builder(_n),
        subtree_size_builder(_n),
        n(euler_tour_builder::n),
        tree(euler_tour_builder::tree),
        rt(euler_tour_builder::rt),
        cur(_n),
        parents(_n) {}
  vector<int> ans;
  void process() {
    euler_tour_builder::process();
    subtree_size_builder::process();
    csz.resize(n);
    for (int i = 0; i < ((int)(n)); ++i) {
      csz[tin(i)] = sz[i];
      cur.update(tin(i), sz[i]);
    }
    ans.resize(n);
    dfs(rt, -1);
  }
  void set_root(int v) {
    euler_tour_builder::set_root(v);
    subtree_size_builder::set_root(v);
  }
  void add_edge(int u, int v) {
    euler_tour_builder::add_edge(u, v);
    subtree_size_builder::add_edge(u, v);
  }
};
int main() {
  int n = IO.readInt<int>();
  prob_G G(n);
  for (int i = 0; i < ((int)(n)); ++i) {
    int u = IO.readInt<int>();
    int v = IO.readInt<int>();
    if (u == 0) {
      G.set_root(v - 1);
      continue;
    }
    u--;
    v--;
    G.add_edge(u, v);
  }
  G.process();
  for (int x : G.ans) IO.writeInt(x);
  IO.writeEndl();
  return 0;
}
