問題文
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) 。
- 继续2 从行N-1行表示图的边缘信息。 第i行显示由边连接的顶点。 x_i 和 y_i用空格分隔。
- 继续1+N 边缘 一个整数,表示(a,b)的候选者数量 Q (1≦Q≦100,000) 。
- 继续2+N 从行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 点。
出力
对于所有附加候选边,计算将它们添加到原始图中时创建的循环长度,1 从行 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