1965: 领导领导

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：58 解决：27

题目描述

某大型企业的组织架构呈树形结构，每个员工对应一个唯一编号。CEO 作为组织架构的最高负责人，所有员工均直接或间接隶属于 CEO，且每个员工仅有一位直属上级。
为了高效处理跨部门协作需求，HR 部门需要查询任意两位员工的「最近共同领导」—— 即两位员工在组织架构中，距离两人都最近的共同上级。

输入

第一行包含三个正整数 N、M、S，分别表示企业的员工总数、查询次数、CEO 的员工编号。

接下来 N-1 行，每行包含两个正整数 x、y，表示员工 x 和员工 y 是直属上下级关系。

接下来 M 行，每行包含两个正整数 a、b，表示查询员工 a 和员工 b 的最近共同领导。

输出

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

样例输入 复制 

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

样例输出 复制 

4
4
1
4
4

提示

对于  的数据，，。

来源/分类