题目描述

给定一棵 $n$ 个结点的树（结点标号 $1 \dots n$ ）以及树中结点的边，结点 $s$ 为树的根。

有 $m$ 次询问，请求出每次询问的两个结点 $x$ 和 $y$ 的最近的公共祖先结点。

输入

第 $1$ 行输入 $3$ 个整数 $n$ 、 $m$ 、 $s$ （ $n≤500000$ ， $m≤500000$ ， $1≤s≤n$ ）；

接下来 $n-1$ 行，每行两个整数 $a$ 和 $b$ ，结点 $a$ 和 $b$ 是父子关系，但不保证 $a$ 是 $b$ 的父，数据保证一定能构成树；

接下来 $m$ 行，每行两个整数 $x$ ， $y$ ，表示要求出 $x$ 和 $y$ 结点的公共祖先。

输出

输出 $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

来源

树