问题描述
给定一棵包含 n 个节点的有根树（根节点为 $1$），处理 m 次查询，每次查询两个节点的最近公共祖先（$LCA$）。要求使用倍增算法实现高效查询。

输入格式

• 第 $1$ 行：一个整数 n（$2 ≤ n ≤ 10^5$），表示树的节点数。
• 第 $2$ 至 $n$ 行：每行两个整数 u 和 v，表示节点 u 和 v 之间有一条边。
• 第 $n+1$ 行：一个整数 m（$1 ≤ m ≤ 10^5$），表示查询次数。
• 第 $n+2$ 至 $n+m+1$ 行：每行两个整数 a 和 b，表示查询的两个节点。

输出格式

• 输出共 m 行，每行一个整数，表示对应查询的 $LCA$ 结果。

示例输入

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

示例输出

3
1