AT_abc460_f.Farthest Pair Query

There is a tree with $N$ vertices. The vertices are numbered $1, 2, \ldots, N$, and the $i$-th edge connects vertices $U_i$ and $V_i$.

Initially, all vertices are painted black.

Process $Q$ queries of the following form in order and find the answer for each query.

• An integer $x$ $(1 \leq x \leq N)$ is given. If vertex $x$ is white, repaint it black; if vertex $x$ is black, repaint it white. Then, find the maximum distance between two black vertices. Here, the distance between two vertices on a tree is the number of edges in the simple path between them.

In the given inputs, there are always at least two black vertices when processing the queries in order.

有一棵包含 $N$ 个顶点的树。顶点编号为 $1, 2, \ldots, N$，其中第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。

初始时，所有顶点均为黑色。

按顺序处理 $Q$ 个如下形式的查询，并对每个查询输出答案：

• 给定一个整数 $x$（$1 \leq x \leq N$）。若顶点 $x$ 为白色，则将其涂成黑色；若为黑色，则将其涂成白色。然后，求所有黑色顶点之间两两距离的最大值。此处，树上两个顶点之间的距离定义为它们之间唯一简单路径所含的边数。

在给定的输入中，按顺序处理查询时，黑色顶点的数量始终不少于两个。

The input is given from Standard Input in the following format, where $\text{query}_i$ denotes the $i$-th query:

$N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$
$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

Each query is given in the following format:

$x$

输入从标准输入中以如下格式给出，其中 $\text{query}_i$ 表示第 $i$ 个查询：

$N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$
$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

每个查询的格式如下：

$x$

Output $Q$ lines.

The $i$-th line should contain the answer for the $i$-th query when processed in order.

输出 $Q$ 行。

第 $i$ 行应包含按顺序处理的第 $i$ 个查询的答案。

Sample 1 Explanation:

• After the repainting in the $1$st query, the black vertices are $2, 3, 4, 5, 6, 7$. The distance between vertices $4$ and $6$ is $4$, and the answer is $4$.
• After the repainting in the $2$nd query, the black vertices are $2, 3, 5, 6, 7$. The distance between vertices $2$ and $6$ is $3$, and the answer is $3$.
• After the repainting in the $3$rd query, the black vertices are $3, 5, 6, 7$. The distance between vertices $5$ and $6$ is $3$, and the answer is $3$.
• After the repainting in the $4$th query, the black vertices are $3, 5, 7$. The distance between vertices $5$ and $7$ is $2$, and the answer is $2$.
• After the repainting in the $5$th query, the black vertices are $5, 7$. The distance between vertices $5$ and $7$ is $2$, and the answer is $2$.
• After the repainting in the $6$th query, the black vertices are $1, 5, 7$. The distance between vertices $1$ and $5$ is $3$, and the answer is $3$.
• After the repainting in the $7$th query, the black vertices are $5, 7$. The distance between vertices $5$ and $7$ is $2$, and the answer is $2$.
• After the repainting in the $8$th query, the black vertices are $4, 5, 7$. The distance between vertices $4$ and $5$ is $3$, and the answer is $3$.
• After the repainting in the $9$th query, the black vertices are $4, 5, 6, 7$. The distance between vertices $4$ and $6$ is $4$, and the answer is $4$.

Note that the examples given above are just one instance achieving the maximum value.

Constraints

• $3 \leq N \leq 10^5$
• $1 \leq U_i, V_i \leq N$
• The given graph is a tree.
• $1 \leq Q \leq 10^5$
• For each query, $1 \leq x \leq N$.
• There are always at least two black vertices.
• All input values are integers.

样例 1 解释：

• 第 $1$ 次查询重绘后，黑色顶点为 $2, 3, 4, 5, 6, 7$。顶点 $4$ 与 $6$ 之间的距离为 $4$，答案为 $4$。
• 第 $2$ 次查询重绘后，黑色顶点为 $2, 3, 5, 6, 7$。顶点 $2$ 与 $6$ 之间的距离为 $3$，答案为 $3$。
• 第 $3$ 次查询重绘后，黑色顶点为 $3, 5, 6, 7$。顶点 $5$ 与 $6$ 之间的距离为 $3$，答案为 $3$。
• 第 $4$ 次查询重绘后，黑色顶点为 $3, 5, 7$。顶点 $5$ 与 $7$ 之间的距离为 $2$，答案为 $2$。
• 第 $5$ 次查询重绘后，黑色顶点为 $5, 7$。顶点 $5$ 与 $7$ 之间的距离为 $2$，答案为 $2$。
• 第 $6$ 次查询重绘后，黑色顶点为 $1, 5, 7$。顶点 $1$ 与 $5$ 之间的距离为 $3$，答案为 $3$。
• 第 $7$ 次查询重绘后，黑色顶点为 $5, 7$。顶点 $5$ 与 $7$ 之间的距离为 $2$，答案为 $2$。
• 第 $8$ 次查询重绘后，黑色顶点为 $4, 5, 7$。顶点 $4$ 与 $5$ 之间的距离为 $3$，答案为 $3$。
• 第 $9$ 次查询重绘后，黑色顶点为 $4, 5, 6, 7$。顶点 $4$ 与 $6$ 之间的距离为 $4$，答案为 $4$。

注意：上述示例仅为达到最大值的一种可能情形。

约束条件

• $3 \leq N \leq 10^5$
• $1 \leq U_i, V_i \leq N$
• 给定图是一棵树。
• $1 \leq Q \leq 10^5$
• 对于每次查询，$1 \leq x \leq N$。
• 黑色顶点数量始终不少于两个。
• 所有输入值均为整数。