题目描述

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

对于两个结点 $u,v$，它们的最近公共祖先记为

$$\operatorname{LCA}(u,v)$$

它表示：在以 $s$ 为根的这棵树中，同时是 $u$ 和 $v$ 的祖先，并且深度最大的那个结点。

现在有 $m$ 次询问。每次给出两个结点 $u,v$，你需要输出

$$\operatorname{LCA}(u,v)$$

的值。

输入格式

输入共 $n+m$ 行。

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

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

接下来 $m$ 行，每行输入两个整数 $u,v$，表示一次询问，要求输出在以 $s$ 为根时的

$$\operatorname{LCA}(u,v)$$

满足：

$$1 \le n \le 2 \times 10^5,\qquad 1 \le m \le 2 \times 10^5,\qquad 1 \le s \le n$$$$1 \le u,v \le n$$

题目保证输入的图是一棵树。

输出格式

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