2200 - 树的公共祖先(LCA)(3)

题目描述

给定一棵 n 个结点的树(结点标号 1 \dots n )以及树中结点的边,结点 s 为树的根。

m 次询问,请求出每次询问的两个结点 xy 的最近的公共祖先结点。

输入

1 行输入 3 个整数 nmsn≤500000m≤5000001≤s≤n);

接下来 n-1 行,每行两个整数 ab ,结点 ab 是父子关系,但不保证 ab 的父,数据保证一定能构成树;

接下来 m 行,每行两个整数 xy,表示要求出 xy 结点的公共祖先。

输出

输出 m 行,每行一个整数,表示 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
来源

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 提高


上一题 下一题