最近公共祖先

题目描述:

编写一个程序，查找一棵含有 n 个节点的树中 m 组两个不同节点的最近公共祖先。

输入格式:

第一行两个整数 n 和 q，为树上节点的数目和查询数。节点标号为整数 1,2,…,n。
之后 n−1 行每一行包含一对整数，代表边——第一个整数是第二个整数的父节点。请注意，一个具有 n 个节点的树有 n−1 条边。
之后 q 行查询，每行两个整数，表示要查询的两个节点的标号。（输入保证有且只有一棵树）

输出格式:

q 行，每行一个整数，为此次查询的最近公共祖先的标号。

样例输入:

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

样例输出:

2
2
5
5
5
5

提示:

2≤n,m≤5⋅10​^5​​

时间限制: 2000ms
空间限制: 256MB

---