题目内容

在浩瀚的银河联邦中，有一个由 $n$ 个空间站和 $n-1$ 条空间航道组成的骨干网络。该网络连通且无环，从任意一个空间站出发都可以沿着航路到达其他所有空间站。

通常，整个网络以编号为 $1$ 的空间站作为核心调度站。但在进行舰队演习时，指挥部会临时指定某个空间站 $r$ 作为新的调度中心，此时整个网络的层次关系会以 $r$ 为根重新确定。

在每次演习中，你需要快速回答：若以 $r$ 为调度中心，从 $u$ 与 $v$ 出发前往 $r$ 的两条航路，会在哪个空间站汇聚后不再分叉？我们称这个空间站为 $u$ 和 $v$ 在当前根 $r$ 下的 最深公共聚合点。

形式化地说，给定一棵有根树，节点 $u$ 和 $v$ 的最深公共聚合点是指在根到 $u$ 的路径和根到 $v$ 的路径上都出现的节点中，距离根最远的那个节点。

现在给定网络的结构，你需要处理 $q$ 次演习询问，每次给出三个节点 $(r, u, v)$，输出以 $r$ 为根时 $u$ 与 $v$ 的最深公共聚合点。

数据约束

• 单组测试数据中，空间站数量 $n$ 和询问次数 $q$ 均不超过 $2 \times 10^5$。
• 所有测试数据的 $n$ 之和与 $q$ 之和均不超过 $2 \times 10^5$。
• 空间站编号均为 $1$ 到 $n$ 的整数。

输入描述

第一行输入一个整数 $T$（$1 \le T \le 2 \times 10^5$），表示测试数据组数。

每组测试数据的格式如下：

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \times 10^5$），分别表示空间站数量和演习询问次数。

接下来 $n-1$ 行，每行包含两个整数 $x_i, y_i$（$1 \le x_i, y_i \le n$），表示一条空间航道直接连接 $x_i$ 和 $y_i$。

接下来 $q$ 行，每行包含三个整数 $r_i, u_i, v_i$（$1 \le r_i, u_i, v_i \le n$），表示一次演习询问，临时调度中心为 $r_i$，需要求 $u_i$ 和 $v_i$ 的最深公共聚合点。

输出描述

对于每组测试数据，输出 $q$ 行，每行一个整数，依次表示每次询问的答案。

样例1

输入

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

输出

3
4
5

说明

该样例包含 1 组测试数据，网络由 5 个空间站构成一条链：1-2-3-4-5，以 1 为原根。

对于第 1 次查询 3 1 5：计算原根下的 $a = LCA(1,5) = 1$，$b = LCA(1,3) = 1$，$c = LCA(5,3) = 3$。满足 $a = b$，因此答案取 $c = 3$。当临时调度中心变为 3 时，1 和 5 的路径在 3 汇聚，最深公共聚合点为 3。

第 2 次查询 2 4 5：$a = LCA(4,5) = 4$，$b = LCA(4,2) = 2$，$c = LCA(5,2) = 2$。此时 $a eq b$ 且 $a eq c$，答案取 $a = 4$。在以 2 为根的层次下，4 与 5 的最深公共聚合点为 4。

第 3 次查询 1 5 5：$a = LCA(5,5) = 5$，$b = LCA(5,1) = 1$，$c = LCA(5,1) = 1$。$a eq b$ 且 $a eq c$，答案取 $a = 5$。当查询的两个空间站相同时，聚合点就是它们自身。

样例2

输入

2
3 3
1 2
1 3
2 2 3
3 2 3
1 2 3
4 3
1 2
2 3
3 4
2 1 4
3 1 2
4 1 1

输出

2
3
1
2
2
1

说明

本样例包含 2 组测试数据。

第一组数据：网络为星型，节点 1 连接 2 和 3。

• 查询 2 2 3：原根下 $a = LCA(2,3) = 1$，$b = LCA(2,2) = 2$，$c = LCA(3,2) = 1$。满足 $a = c$，答案取 $b = 2$。以 2 为根时，2 和 3 的最深公共聚合点为 2。
• 查询 3 2 3：$a = 1$，$b = 1$，$c = 3$，$a = b$，答案 $c = 3$。以 3 为根时，聚合于 3。
• 查询 1 2 3：所有 $LCA$ 均为 1，答案 1。

第二组数据：链 1-2-3-4，以 1 为根。

• 查询 2 1 4：$a = LCA(1,4) = 1$，$b = LCA(1,2) = 1$，$c = LCA(4,2) = 2$，$a = b$，答案 2。
• 查询 3 1 2：$a = 1$，$b = 1$，$c = 2$，同理答案 2。
• 查询 4 1 1：两点相同，聚合点为自身 1。