A7138 | 閉路

给定一个包含 $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$。
- 所有候选新边都不在原图中，且不为自环。

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