给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

第一行包含三个正整数 m root n，分别表示树的边数、树根结点的序号、询问次数。
接下来 m 行每行包含两个正整数 x, y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来n行每行包含两个正整数，表示结点1与结点2，用于询问结点1与结点2的最近公共祖先

n行，每行一个正整数，表示两个结点之间的最近公共祖先

样例说明：
该图结构如下：



第一次询问：2, 4 的最近公共祖先，故为 4。
第二次询问：3,2 的最近公共祖先，故为 4。
第三次询问：3,5 的最近公共祖先，故为 1。
第四次询问：1,2 的最近公共祖先，故为 4。
第五次询问：4,5 的最近公共祖先，故为 4。
故输出依次为 4, 4, 1, 4, 4。






对于 30% 的数据，N≤10，M≤10。
对于 70% 的数据，N≤10000，M≤10000。
对于 100% 的数据，N≤500000，M≤500000。

数据结构 树