CF768G.The Winds of Winter

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.

给定一棵包含 $n$ 个节点的有根树。夜王恰好从树中移除一个节点及其所有关联的边。该操作将树分割为一片森林。被移除的节点不属于该森林。

森林中某棵树的根，是指该树中没有父节点的节点。我们定义该森林的强度（strength） 为森林中最大树的大小（即节点数）。

琼·雪诺希望最小化该森林的强度。为此，他最多可执行一次如下操作：

他移除某个节点与其父节点之间的边，并在该节点与森林中任意其他节点之间插入一条新边，使得森林中的树的总数保持不变。

对每个节点 $v$，你需要求出：当节点 $v$ 被移除时，所能得到的森林强度的最小可能值。

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 u__i and v__i (1  ≤  u__i,  v__i  ≤  n) where u__i is the parent of v__i. If u__i = 0 then v__i is the root.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 树中顶点的数量。接下来的 $n$ 行每行包含一对顶点编号 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），其中 $u_i$ 是 $v_i$ 的父节点。若 $u_i = 0$，则 $v_i$ 是根节点。

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.

输出 n 行，每行包含一个整数。其中第 i 行的值应等于：当移除第 i 个节点后，琼恩·雪诺最多执行一次上述操作所形成的森林的强度的最小值。

The tree for first test case is depicted below. When you remove the first node, the tree splits to form the following forest. The strength of this forest is 4. Jon Snow now changes the parent of vertex 10 from 5 to 3. The strength of forest now becomes 3.

第一个测试用例对应的树如下图所示。
当你删除第一个节点时，该树分裂形成如下森林。该森林的强度为 4。
琼恩·雪诺现在将顶点 10 的父节点从 5 更改为 3。此时森林的强度变为 3。