### 问题描述 给你一个无向树，树中共有 $N$ 个结点。每个结点从 $1$ 到 $N$ 编号，且 $1$ 号节点是根节点。你需要实现一个程序，根据给定的两个结点编号，找出它们的最近公共祖先。 首先，我们来详细定义“最近公共祖先”。 **最近公共祖先的定义** 在一个树形结构中，如果我们选取两个节点 $p$ 和 $q$，那么 $p$ 和 $q$ 的最近公共祖先（LCA, Lowest Common Ancestor）可以被定义为这样一个节点 $x$，它同时满足以下条件： 1. $x$ 是 $p$、$q$ 的祖先。 2. $x$ 的深度尽可能大（即 $x$ 距离根的距离尽可能远，距离 $p$、$q$ 节点尽可能近）。 换句话说，最近公共祖先就是从根节点出发，走到 $p$ 和 $q$ 之前的最后一个公共节点。 在给定的问题描述中，你需要从一个无向树中找到两个结点的最近公共祖先。一个无向树可以被看作是一个连通的无向图，其中有 $N$ 个结点和 $N-1$ 条边。而且已经给定了根节点是 $1$ 号节点。在这样的树结构中，每两个节点都有一个唯一的最近公共祖先。 ### 输入格式 第一行包含一个整数 $N$，表示结点的数量。 接下来的 $N-1$ 行，每行包含两个整数 $u$ 和 $v$，表示结点 $u$ 和结点 $v$ 之间有一条边。 下一行包含一个整数 $Q$，表示查询的数量。 接下来的 $Q$ 行，每行包含两个整数 $a$ 和 $b$，你需要为每一对 $a$ 和 $b$ 找出它们的最近公共祖先。 ### 输出格式 对于每一个查询，输出一个整数，表示两个结点的最近公共祖先。 ### 样例输入 ``` 5 1 2 1 3 2 4 2 5 2 4 5 3 5 ``` ### 样例输出 ``` 2 1 ``` ### 样例说明 对于第一个查询，结点 $4$ 和 $5$ 的最近公共祖先是结点 $2$。 对于第二个查询，结点 $3$ 和 $5$ 的最近公共祖先是结点 $1$。 ### 测评数据规模 $1 \leq N \leq 10^5$，$1 \leq Q \leq 10^5$，$1 \leq u, v, a, b \leq N$。