### 问题描述 给定一棵有 $N$ 个节点的树，每个节点有一个唯一的编号，从 $1$ 到 $N$。树的根节点是 $1$ 号节点。接下来，你会得到 $Q$ 个查询。对于每个查询，你将得到两个节点的编号，你的任务是找到这两个节点的最低公共祖先。 ### 输入格式 第一行包含一个整数 $N$，表示树的节点数。 接下来的 $N-1$ 行，每行包含两个整数 $U$ 和 $V$，表示节点 $U$ 和节点 $V$ 之间有一条边。 下一行包含一个整数 $Q$，表示查询的数量。 接下来的 $Q$ 行，每行包含两个整数 $A$ 和 $B$，表示你需要找到节点 $A$ 和节点 $B$ 的最低公共祖先。 ### 输出格式 对于每个查询，输出一行，该行包含一个整数，表示两个节点的最近公共祖先。 ### 样例输入 ``` 5 1 2 1 3 2 4 2 5 3 4 5 3 4 3 5 ``` ### 样例输出 ``` 2 1 1 ``` ### 样例说明 对于第一个查询，$4$ 和 $5$ 的最低公共祖先是 $2$。 对于第二个查询，$3$ 和 $4$ 的最低公共祖先是 $1$。 对于第三个查询，$3$ 和 $5$ 的最低公共祖先是 $1$。 ### 测评数据规模 $2 \leq N \leq 10^5$，$1 \leq Q \leq 10^4$，$1 \leq U, V, A, B \leq N$，题目保证输入的边形成一棵树。