AT_abc014_4.[ABC014D] 閉路

给定一个包含 $n$ 个顶点和 $n-1$ 条边的连通无向图。每个顶点按顺序编号为 $1$ 到 $n$。

在图论中，满足上述条件的图被称为树，并且具有不包含环路的性质。现在，考虑在原图中添加一条不在原图中的新边 $(a, b)$，此时图中恰好会出现一个环。你的任务是，对于所有给定的候选新边，输出每次添加后所形成的环的长度（即环中包含的边数）。需要注意的是，候选新边有 $Q$ 个，请对所有候选边分别输出答案。

输入按以下格式从标准输入给出。

$N$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_{N-1}\ y_{N-1}$
$Q$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_{Q}\ b_{Q}$

• 第 $1$ 行给出一个整数 $N\ (1 \leq N \leq 100,\!000)$，表示图的顶点数。
• 接下来的 $N-1$ 行，每行给出一条边的信息。第 $i$ 行包含用空格分隔的两个整数 $x_i$ 和 $y_i$，表示一条连接顶点 $x_i$ 和 $y_i$ 的边。
• 第 $N$ 行之后的第 $1$ 行，给出一个整数 $Q\ (1 \leq Q \leq 100,\!000)$，表示候选新边的数量。
• 接下来的 $Q$ 行，每行给出一条候选新边的信息。第 $i$ 行包含用空格分隔的两个整数 $a_i$ 和 $b_i$，表示一条连接顶点 $a_i$ 和 $b_i$ 的新边。
• 所有给定的边都连接存在的顶点。
• 图中不包含自环，即对于任意 $i$，都有 $x_i \neq y_i$。
• 图中不包含重边，即对于任意 $i, j\ (i \neq j)$，都有 $x_i \neq x_j$ 或 $y_i \neq y_j$。
• 所有候选新边都不在原图中，且不为自环。

对于每个候选新边，依次输出将其添加到原图后所形成的环的长度，每个答案占一行。输出末尾需换行。

部分分

本题有两个数据集，每个数据集对应部分分。

• 对于 $Q=1$ 的数据集 1，答对可获得 $30$ 分。
• 对于没有额外限制的数据集 2，答对可获得 $70$ 分（与上述数据集分开计分）。

样例说明 1

图示如下所示。

由 ChatGPT 4.1 翻译