问题文

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

在图论中，满足这种条件的图被称为树，它具有不包含回路的性质。对于这个图，我们考虑在原图中添加一条不包含的附加边 $(a, b)$，并思考这个图中恰好包含一个回路。你的任务是输出对于这样的图，回路的长度（包含的边的数量）。然而，存在多个可能的附加边，我们将会给出 $Q$ 个附加边的候选，请输出所有候选的答案。

输入

从标准输入读入输入数据，输入格式如下：

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

• 第 $1$ 行为一个整数 $N$，表示图的顶点数 $(1≦N≦100,000)$。
• 接下来的 $N-1$ 行，表示图的边信息。第 $i$ 行包含由边连接的顶点 $x_i$ 和 $y_i$。
• 第 $1+N$ 行为一个整数 $Q$，表示候选边的数量 $(1≦Q≦100,000)$。
• 接下来的 $Q$ 行，表示第 $i$ 个候选边的信息。第 $i$ 行包含由边连接的顶点 $a_i$ 和 $b_i$。
• 所有给定的边都连接了存在的顶点。
• 图中不包含自环。即对于任意的 $i$，$x_i≠y_i$。
• 图中不包含重边。即对于任意的 $i,j(i≠j)$，$x_i≠x_j$ 或者 $y_i≠y_j$。
• 附加边保证是不存在于原图中且不是自环的。

部分点

本问题共有两个数据集，每个数据集的部分得分如下：

• 当 $Q=1$，即满足数据集 1 的条件时，如果答案正确，将给予 $30$ 分。
• 对于没有其他限制的数据集 2 ，如果答案正确，将额外给予 $70$ 分。

输出

对于每个候选边，按照顺序输出将其加入原图后形成的回路的长度，共 $Q$ 行。输出结束后换行。

示例1

5
1 2
1 3
1 4
4 5
3
2 3
2 5
2 4

输出示例1

3
4
3

图示如下：

示例2

6
1 2
2 3
3 4
4 5
5 6
4
1 3
1 4
1 5
1 6

输出示例2

3
4
5
6

示例3

7
3 1
2 1
2 4
2 5
3 6
3 7
5
4 5
1 6
5 6
4 7
5 3

输出示例3

3
3
5
5
4