描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

格式

输入格式

第一行包含三个正整数 \(N,M,S\),分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 \(N-1\)行每行包含两个正整数 \(x, y\)，表示 \(x\) 结点和\( y\)结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 \(M\)行每行包含两个正整数\( a, b\)，表示询问\( a\)结点和\( b \)结点的最近公共祖先。

输出格式

输出包含 \(M\) 行，每行包含一个正整数，依次为每一个询问的结果。

样例1

样例输入1

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

样例输出1

4
4
1
4
4

样例解释

该树结构如下：

第一次询问：\(2, 4\)的最近公共祖先，故为 \(4\)。

第二次询问：\(3, 2 \)的最近公共祖先，故为 \(4\)。

第三次询问：\(3, 5\) 的最近公共祖先，故为 \(1\)。

第四次询问：\(1, 2\)的最近公共祖先，故为\( 4\)。

第五次询问：\(4, 5\)的最近公共祖先，故为\( 4\)。

故输出依次为 \(4, 4, 1, 4, 4\)。

限制

对于 \(100\)% 的数据,\(N≤500000，M≤500000\)。

来源

地址：\(vijos\)，芜湖\(OI\)团队
作者：黑暗路西法\(08\)
模拟赛\(T2\)
\(2022.2.27 bug\)已修复