你好！我是你的OI金牌教练。

我们已经完成了图论中的最短路（Dijkstra, Floyd）、连通性（并查集）、生成树（Kruskal）以及拓扑排序的学习。同时也接触过树的基础遍历（求子树大小）。

今天，我们将回到文化繁荣的北宋，结合 “宗法制与族谱（苏氏族谱）” 的历史背景，学习树上极其重要、也是 GESP 6级 乃至 7级的核心算法——最近公共祖先 (Lowest Common Ancestor, LCA)。

这道题在知识点上的递进关系体现为：

1. 从树的一次性遍历（如求子树大小）进阶到树上的多次快速查询。
2. 引入了倍增 (Binary Lifting) 思想。这是继“二分答案”之后，对 $\log N$ 复杂度优化的又一次深刻应用。

第一部分：背景知识讲解

1. 宗法制与族谱 (The Clan System & Genealogy)

中国古代非常重视血缘亲情和家族传承。宋代大文豪苏成（号老泉）编撰的《苏氏族谱》，创立了“苏式族谱”体例，强调“明世次，别亲疏”。 在族谱中，家族成员的关系构成了一棵巨大的树。

• 始祖：树的根节点。
• 父子关系：树的边。

2. 辈分与亲疏

在家族中，要判断两个人的关系远近，或者确定两人在家族中的“共同源头”，就需要找到他们的最近公共祖先。

• 例如：你和你亲兄弟的最近公共祖先是父亲。
• 你和你堂兄弟的最近公共祖先是祖父。

3. 算法模型：LCA (Lowest Common Ancestor)

在有根树中，两个节点 $u$ and $v$ 的公共祖先是指既是 $u$ 的祖先又是 $v$ 的祖先的节点（包括 $u, v$ 自身）。 其中，深度最大（位置最低，离 $u, v$ 最近）的那个祖先，称为最近公共祖先 (LCA)。

• 暴力法：让 $u$ 和 $v$ 两个点顺着父亲节点一步步往上爬，直到相遇。如果树很高（退化成链），单次查询最坏 $O(N)$。如果有 $Q$ 次查询，总复杂度 $O(QN)$，会超时。
• 倍增法：利用 $2^k$ 的跳跃能力，预处理出每个节点往上跳 $1, 2, 4, 8 \dots$ 步到达的祖先。查询时可以在 $O(\log N)$ 时间内找到 LCA。

第二部分：题目内容

题目名称：苏氏族谱 (The Su Family Genealogy)

题目描述

北宋眉山苏氏家族人才辈出，苏洵、苏轼、苏辙“三苏”更是名垂青史。为了理清家族庞大的血脉关系，苏洵决定重新修订族谱。

族谱中共有 $N$ 位家族成员，编号为 $1$ 到 $N$。其中，编号为 $1$ 的成员是始祖（根节点）。 除了始祖外，每位成员都有且仅有一位父亲。

现在，有 $Q$ 次询问。每次询问给出两位家族成员的编号 $u$ 和 $v$，请你找出他们的最近公共祖先是谁。

最近公共祖先的定义：在以 $1$ 号为根的树上，找到一个节点 $L$，使得 $L$ 既是 $u$ 的祖先，也是 $v$ 的祖先，并且 $L$ 的深度尽可能大（离 $u, v$ 最近）。 注：一个节点也可以是它自己的祖先。

输入格式

第一行包含两个正整数 $N, Q$。

• $N$ 表示家族成员数量。
• $Q$ 表示询问次数。

接下来 $N-1$ 行，每行包含两个正整数 $x, y$，表示 $x$ 是 $y$ 的父亲（即树上有一条 $x \to y$ 的边）。

接下来 $Q$ 行，每行包含两个正整数 $u, v$，表示一次询问。

输出格式

输出 $Q$ 行，每行一个整数，表示 $u$ 和 $v$ 的最近公共祖先的编号。

输入输出样例 #1

输入：

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

输出：

2
1
2

样例 #1 解释： 树形结构：

      1
     / \
    2   3
   / \
  4   5

1. LCA(4, 5)：4 的祖先是 4, 2, 1；5 的祖先是 5, 2, 1。公共的有 2, 1。最近的是 2。
2. LCA(3, 4)：3 的祖先 3, 1；4 的祖先 4, 2, 1。公共的是 1。
3. LCA(4, 2)：4 的祖先 4, 2, 1；2 的祖先 2, 1。公共的是 2, 1。最近的是 2（2是4的父亲，LCA就是2自己）。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$
• 保证是一棵合法的树，根节点为 1。