#include <bits/stdc++.h>
const int MAXN = 100000 + 10;
int n, e, beg[MAXN], nex[MAXN << 1], to[MAXN << 1], st[MAXN], ed[MAXN],
    dfn[MAXN], cnt, fa[MAXN], top[MAXN], hson[MAXN], size[MAXN], root;
std::pair<int, int> rest[MAXN];
std::vector<std::pair<int, int> > ban, val, ext;
template <typename T>
inline void read(T &x) {
  T data = 0, w = 1;
  char ch = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') w = -1, ch = getchar();
  while (ch >= '0' && ch <= '9')
    data = ((T)data << 3) + ((T)data << 1) + (ch ^ '0'), ch = getchar();
  x = data * w;
}
template <typename T>
inline void write(T x, char ch = '\0') {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
  if (ch != '\0') putchar(ch);
}
template <typename T>
inline bool chkmin(T &x, T y) {
  return y < x ? (x = y, true) : false;
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return y > x ? (x = y, true) : false;
}
template <typename T>
inline T min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
inline T max(T x, T y) {
  return x > y ? x : y;
}
struct ChairMan_Tree {
  int root[MAXN], lc[MAXN << 7], rc[MAXN << 7], sum[MAXN << 7], cnt;
  inline void Update(int &rt, int last, int l, int r, int ps) {
    rt = ++cnt;
    sum[rt] = sum[last] + 1;
    lc[rt] = lc[last];
    rc[rt] = rc[last];
    if (l == r)
      return;
    else {
      if (ps <= ((l + r) >> 1))
        Update(lc[rt], lc[last], l, ((l + r) >> 1), ps);
      else
        Update(rc[rt], rc[last], ((l + r) >> 1) + 1, r, ps);
    }
  }
  inline int Query(int now, int last, int l, int r, int ps, int opt) {
    if (!(sum[now] - sum[last])) return opt ? n + 1 : 0;
    if (l == r) {
      if (!opt)
        return (sum[now] - sum[last]) ? l : 0;
      else
        return (sum[now] - sum[last]) ? l : n + 1;
    } else {
      if (!opt) {
        int res = 0;
        if (ps > ((l + r) >> 1))
          res = Query(rc[now], rc[last], ((l + r) >> 1) + 1, r, ps, opt);
        if (res > 0) return res;
        return Query(lc[now], lc[last], l, ((l + r) >> 1), ps, opt);
      } else {
        int res = n + 1;
        if (ps <= ((l + r) >> 1))
          res = Query(lc[now], lc[last], l, ((l + r) >> 1), ps, opt);
        if (res <= n) return res;
        return Query(rc[now], rc[last], ((l + r) >> 1) + 1, r, ps, opt);
      }
    }
  }
};
ChairMan_Tree T;
inline void insert(int x, int y) {
  to[++e] = y;
  nex[e] = beg[x];
  beg[x] = e;
}
inline void dfs1(int x, int f) {
  int res = 0;
  fa[x] = f;
  size[x] = 1;
  for (register int i = beg[x]; i; i = nex[i])
    if (to[i] == f)
      continue;
    else {
      dfs1(to[i], x);
      size[x] += size[to[i]];
      if (chkmax(res, size[to[i]])) hson[x] = to[i];
    }
}
inline void dfs2(int x, int tp) {
  st[x] = ++cnt;
  top[x] = tp;
  dfn[cnt] = x;
  if (hson[x]) dfs2(hson[x], tp);
  for (register int i = beg[x]; i; i = nex[i])
    if (to[i] == fa[x] || to[i] == hson[x])
      continue;
    else
      dfs2(to[i], to[i]);
  ed[x] = cnt;
}
inline void init() {
  dfs1(root, 0);
  dfs2(root, root);
  for (register int i = (1), iend = (n); i <= iend; ++i)
    T.Update(T.root[i], T.root[i - 1], 1, n, size[dfn[i]]);
}
inline int find(std::pair<int, int> mn, std::pair<int, int> mx, int x) {
  int key = (mx.first - mn.first) / 2, ans = max(mn.first, mx.first),
      sz = size[x];
  if (mx.second != 1) {
    int u = mx.second;
    int x1 = T.Query(T.root[ed[u]], T.root[st[u] - 1], 1, n, key, 0);
    int x2 = T.Query(T.root[ed[u]], T.root[st[u] - 1], 1, n, key, 1);
    chkmin(ans, max(mn.first + x1, mx.first - x1));
    chkmin(ans, max(mn.first + x2, mx.first - x2));
  } else {
    ban.clear(), val.clear(), ext.clear();
    ban.push_back(std::make_pair(st[x], ed[x]));
    x = fa[x];
    while (x) {
      ban.push_back(std::make_pair(st[top[x]], st[x]));
      ext.push_back(std::make_pair(st[top[x]], st[x]));
      x = fa[top[x]];
    }
    std::sort(ban.begin(), ban.end());
    int t = ban.size() - 1;
    if (ban[0].first != 1) val.push_back(std::make_pair(1, ban[0].first - 1));
    if (ban[t].second != n) val.push_back(std::make_pair(ban[t].second + 1, n));
    for (register int i = (1), iend = (t); i <= iend; ++i)
      if (ban[i].first - ban[i - 1].second > 1)
        val.push_back(std::make_pair(ban[i - 1].second + 1, ban[i].first - 1));
    for (auto v : val) {
      int x1 = T.Query(T.root[v.second], T.root[v.first - 1], 1, n, key, 0);
      int x2 = T.Query(T.root[v.second], T.root[v.first - 1], 1, n, key, 1);
      chkmin(ans, max(mn.first + x1, mx.first - x1));
      chkmin(ans, max(mn.first + x2, mx.first - x2));
    }
    for (auto v : ext) {
      int x1 =
          T.Query(T.root[v.second], T.root[v.first - 1], 1, n, key + sz, 0) -
          sz;
      int x2 =
          T.Query(T.root[v.second], T.root[v.first - 1], 1, n, key + sz, 1) -
          sz;
      chkmin(ans, max(mn.first + x1, mx.first - x1));
      chkmin(ans, max(mn.first + x2, mx.first - x2));
    }
  }
  return ans;
}
inline int solve(int x) {
  int nt = 0;
  for (register int i = beg[x]; i; i = nex[i])
    if (to[i] == fa[x])
      continue;
    else
      rest[++nt] = std::make_pair(size[to[i]], to[i]);
  if (n - size[x]) rest[++nt] = std::make_pair(n - size[x], 1);
  std::sort(rest + 1, rest + nt + 1);
  int ans = n;
  if (nt == 1) ans = rest[nt].first;
  if (nt >= 2) ans = max(find(rest[1], rest[nt], x), rest[nt - 1].first);
  return ans;
}
int main() {
  read(n);
  int p;
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (register int i = (1), iend = (n); i <= iend; ++i) {
    int u, v;
    read(u);
    read(v);
    if (!u)
      root = v;
    else
      insert(u, v), insert(v, u);
  }
  init();
  for (register int i = (1), iend = (n); i <= iend; ++i) write(solve(i), '\n');
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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>

### Response

```cpp
#include <bits/stdc++.h>
const int MAXN = 100000 + 10;
int n, e, beg[MAXN], nex[MAXN << 1], to[MAXN << 1], st[MAXN], ed[MAXN],
    dfn[MAXN], cnt, fa[MAXN], top[MAXN], hson[MAXN], size[MAXN], root;
std::pair<int, int> rest[MAXN];
std::vector<std::pair<int, int> > ban, val, ext;
template <typename T>
inline void read(T &x) {
  T data = 0, w = 1;
  char ch = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') w = -1, ch = getchar();
  while (ch >= '0' && ch <= '9')
    data = ((T)data << 3) + ((T)data << 1) + (ch ^ '0'), ch = getchar();
  x = data * w;
}
template <typename T>
inline void write(T x, char ch = '\0') {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
  if (ch != '\0') putchar(ch);
}
template <typename T>
inline bool chkmin(T &x, T y) {
  return y < x ? (x = y, true) : false;
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return y > x ? (x = y, true) : false;
}
template <typename T>
inline T min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
inline T max(T x, T y) {
  return x > y ? x : y;
}
struct ChairMan_Tree {
  int root[MAXN], lc[MAXN << 7], rc[MAXN << 7], sum[MAXN << 7], cnt;
  inline void Update(int &rt, int last, int l, int r, int ps) {
    rt = ++cnt;
    sum[rt] = sum[last] + 1;
    lc[rt] = lc[last];
    rc[rt] = rc[last];
    if (l == r)
      return;
    else {
      if (ps <= ((l + r) >> 1))
        Update(lc[rt], lc[last], l, ((l + r) >> 1), ps);
      else
        Update(rc[rt], rc[last], ((l + r) >> 1) + 1, r, ps);
    }
  }
  inline int Query(int now, int last, int l, int r, int ps, int opt) {
    if (!(sum[now] - sum[last])) return opt ? n + 1 : 0;
    if (l == r) {
      if (!opt)
        return (sum[now] - sum[last]) ? l : 0;
      else
        return (sum[now] - sum[last]) ? l : n + 1;
    } else {
      if (!opt) {
        int res = 0;
        if (ps > ((l + r) >> 1))
          res = Query(rc[now], rc[last], ((l + r) >> 1) + 1, r, ps, opt);
        if (res > 0) return res;
        return Query(lc[now], lc[last], l, ((l + r) >> 1), ps, opt);
      } else {
        int res = n + 1;
        if (ps <= ((l + r) >> 1))
          res = Query(lc[now], lc[last], l, ((l + r) >> 1), ps, opt);
        if (res <= n) return res;
        return Query(rc[now], rc[last], ((l + r) >> 1) + 1, r, ps, opt);
      }
    }
  }
};
ChairMan_Tree T;
inline void insert(int x, int y) {
  to[++e] = y;
  nex[e] = beg[x];
  beg[x] = e;
}
inline void dfs1(int x, int f) {
  int res = 0;
  fa[x] = f;
  size[x] = 1;
  for (register int i = beg[x]; i; i = nex[i])
    if (to[i] == f)
      continue;
    else {
      dfs1(to[i], x);
      size[x] += size[to[i]];
      if (chkmax(res, size[to[i]])) hson[x] = to[i];
    }
}
inline void dfs2(int x, int tp) {
  st[x] = ++cnt;
  top[x] = tp;
  dfn[cnt] = x;
  if (hson[x]) dfs2(hson[x], tp);
  for (register int i = beg[x]; i; i = nex[i])
    if (to[i] == fa[x] || to[i] == hson[x])
      continue;
    else
      dfs2(to[i], to[i]);
  ed[x] = cnt;
}
inline void init() {
  dfs1(root, 0);
  dfs2(root, root);
  for (register int i = (1), iend = (n); i <= iend; ++i)
    T.Update(T.root[i], T.root[i - 1], 1, n, size[dfn[i]]);
}
inline int find(std::pair<int, int> mn, std::pair<int, int> mx, int x) {
  int key = (mx.first - mn.first) / 2, ans = max(mn.first, mx.first),
      sz = size[x];
  if (mx.second != 1) {
    int u = mx.second;
    int x1 = T.Query(T.root[ed[u]], T.root[st[u] - 1], 1, n, key, 0);
    int x2 = T.Query(T.root[ed[u]], T.root[st[u] - 1], 1, n, key, 1);
    chkmin(ans, max(mn.first + x1, mx.first - x1));
    chkmin(ans, max(mn.first + x2, mx.first - x2));
  } else {
    ban.clear(), val.clear(), ext.clear();
    ban.push_back(std::make_pair(st[x], ed[x]));
    x = fa[x];
    while (x) {
      ban.push_back(std::make_pair(st[top[x]], st[x]));
      ext.push_back(std::make_pair(st[top[x]], st[x]));
      x = fa[top[x]];
    }
    std::sort(ban.begin(), ban.end());
    int t = ban.size() - 1;
    if (ban[0].first != 1) val.push_back(std::make_pair(1, ban[0].first - 1));
    if (ban[t].second != n) val.push_back(std::make_pair(ban[t].second + 1, n));
    for (register int i = (1), iend = (t); i <= iend; ++i)
      if (ban[i].first - ban[i - 1].second > 1)
        val.push_back(std::make_pair(ban[i - 1].second + 1, ban[i].first - 1));
    for (auto v : val) {
      int x1 = T.Query(T.root[v.second], T.root[v.first - 1], 1, n, key, 0);
      int x2 = T.Query(T.root[v.second], T.root[v.first - 1], 1, n, key, 1);
      chkmin(ans, max(mn.first + x1, mx.first - x1));
      chkmin(ans, max(mn.first + x2, mx.first - x2));
    }
    for (auto v : ext) {
      int x1 =
          T.Query(T.root[v.second], T.root[v.first - 1], 1, n, key + sz, 0) -
          sz;
      int x2 =
          T.Query(T.root[v.second], T.root[v.first - 1], 1, n, key + sz, 1) -
          sz;
      chkmin(ans, max(mn.first + x1, mx.first - x1));
      chkmin(ans, max(mn.first + x2, mx.first - x2));
    }
  }
  return ans;
}
inline int solve(int x) {
  int nt = 0;
  for (register int i = beg[x]; i; i = nex[i])
    if (to[i] == fa[x])
      continue;
    else
      rest[++nt] = std::make_pair(size[to[i]], to[i]);
  if (n - size[x]) rest[++nt] = std::make_pair(n - size[x], 1);
  std::sort(rest + 1, rest + nt + 1);
  int ans = n;
  if (nt == 1) ans = rest[nt].first;
  if (nt >= 2) ans = max(find(rest[1], rest[nt], x), rest[nt - 1].first);
  return ans;
}
int main() {
  read(n);
  int p;
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (register int i = (1), iend = (n); i <= iend; ++i) {
    int u, v;
    read(u);
    read(v);
    if (!u)
      root = v;
    else
      insert(u, v), insert(v, u);
  }
  init();
  for (register int i = (1), iend = (n); i <= iend; ++i) write(solve(i), '\n');
  return 0;
}

```