题目描述

给定一棵包含 $n$ 个结点的无根树，结点编号为 $1 \sim n$。现在指定结点 $s$ 为树根，从而这棵树被看作一棵以 $s$ 为根的有根树。

对于两个结点 $u, v$，它们的最近公共祖先记为 $\operatorname{LCA}(u,v)$，表示在以 $s$ 为根的这棵树中，同时是 $u$ 和 $v$ 的祖先，并且深度最大的那个结点。

现在有 $m$ 次询问。每次给出两个结点 $u, v$，你需要输出 $\operatorname{LCA}(u,v)$ 的值。

输入格式

第一行包含三个整数 $n, m, s$，分别表示结点个数、询问个数和树根编号。

接下来 $n-1$ 行，每行包含两个整数 $u, v$，表示树中存在一条连接结点 $u$ 和 $v$ 的无向边。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示一次询问，要求输出在以 $s$ 为根时 $\operatorname{LCA}(u,v)$ 的值。

输出格式

输出共 $m$ 行。对于每次询问，输出一行一个整数，表示对应的最近公共祖先。

样例

7 5 1
1 2
1 3
2 4
2 5
3 6
6 7
4 5
4 6
7 6
7 3
5 7

2
1
6
3
1

数据范围与提示

• $1 \le n \le 2 \times 10^5$
• $1 \le m \le 2 \times 10^5$
• $1 \le s \le n$
• $1 \le u, v \le n$
• 输入的图一定是一棵树。