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 翻译