LCA

题目描述

Orange很喜欢树论算法LCA(最近公共祖先)，但不幸的是，Orange只有一颗无根树，而无根树是无法求LCA的。于是Orange决定自己设置一个树根，这样就又可以求LCA啦。

现在，Orange会有 $q$ 次提问，每次询问给出 $R,u,v$，询问在 $R$ 作为树根的前提下，节点 $u$ 和 $v$ 的LCA。请你回答Orange的所有提问。

输入格式

第一行为2个整数 $n$ 和 $q$。表示无根树的大小和询问次数。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示树的一条边。 接下来 $q$ 行，每行3个整数 $R,u,v$，表示一次询问。

数据范围

$n,q \le 2 \times 10^5$ $1 \le u, v, R, \le n$

输出格式

每次询问输出一个答案，占一行。

样例 #1

样例输入 #1

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

样例输出 #1

1
2
5
2