题目描述

有根树在计算机科学工程领域是一个人人熟知的数据结构类型。下面是一个例子。

\(\text{8->(1,4,5)；1->(13,14)；4->(6,10)；5->(9)；6->(7,15)；10->(2,11,16)；16->(3,12)}\)；

在这个图中，每个点都是由 \({1, 2,...,16}\)中的某个数字标记的。\(8\) 号点是树的根。如果 \(x\) 号点在 \(y\) 号点到根的路径上，则 \(x\) 是 \(y\) 的祖先。比如 \(4\) 是 \(16\) 的祖先，\(10\) 也是。事实上，\(8,4,10,16\) 都是 \(16\) 的祖先。记住，一个节点本身就是自己的祖先。再比如 \(8,4,6,7\) 是 \(7\) 的祖先。

如果 \(x\) 既是 \(y\) 的祖先也是 \(z\) 的祖先则称 \(x\) 是 \(y\) 和 \(z\) 公共祖先。也就是说 \(8\) 和 \(4\) 都是 \(16\) 和 \(7\) 的公共祖先。

如果 \(x\) 在 \(y\) 和 \(z\) 的所有公共祖先中距离 \(y\) 和 \(z\) 最近，则 \(x\) 是 \(y\) 和 \(z\) 的最近公共祖先。也就是说 \(4\) 是 \(16\) 和 \(7\) 的最近公共祖先而不是 \(8\)，因为 \(4\) 比 \(8\) 更近。

再举一些例子：节点 \(2\) 和 \(3\) 的最近共同祖先是节点 \(10\)，节点 \(6\) 和 \(13\) 的最近共同祖先是节点 \(8\)，节点 \(4\) 和 \(12\) 的最近共同祖先是节点 \(4\)。在最后一个例子中，如果 \(Y\) 是 \(Z\) 的祖先，那么 \(Y\) 和 \(Z\) 的最近共同祖先是 \(Y\)。

编写一个程序，找出树中两个不同节点的最近共同祖先。

格式

输入格式

第一行，\(N\)和 \(M\) 表示节点数和询问数，节点编号 \(1\) 至 \(N\)；

以下 \(N-1\) 行，每行两个整数 \(a\) 和 \(b\) ，表示 \(a\) 是 \(b\) 的父亲节点；

之后 \(M\) 行，每行两个不相同的数，表示询问它们的最近共同祖先。

输出格式

\(M\) 行，每行一个数表示对应的询问结果。

样例1

样例输入1

16 1
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7

样例输出1

4

限制

时间：\(1s\) 空间：\(256M\)
对于 \(100\%\) 的数据：\(1<=N,M<=2×10^5\)

来源

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)
模拟赛\(T2\)