A7138 | 閉路

$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$。
• 所有候选新边都不在原图中，且不为自环。