题目描述

Y 岛有 $N$ 个城市，有 $N-1$ 条道路连接它们，形成一棵树。乘车经过每条道路的费用都是一样的（可视为 $1$ 单位费用）。

小可可、小卡卡和小 YY 经常想聚会，每次聚会，他们都会选择一个城市，使得三个人到达这个城市的总费用最小。

你需要根据他们每次聚会前所处的位置，为他们选择聚会地点，并输出该地点编号和三人到该地点的总费用。

---

输入格式

第一行两个正整数，$N$ 和 $M$。分别表示城市个数和聚会次数；

后面有 $N-1$ 行，每行用两个正整数 $A$ 和 $B$ 表示编号为 $A$ 和编号为 $B$ 的城市之间有一条路。城市的编号是从 $1$ 到 $N$ 的；

再后面有 $M$ 行，每行用三个正整数表示一次聚会的情况：小可可所在的城市编号，小卡卡所在的城市编号以及小 YY 所在的城市编号。

---

输出格式

一共有 $M$ 行，每行两个数 $P$ 和 $C$，用一个空格隔开。表示第 $i$ 次聚会的地点选择在编号为 $P$ 的城市，总共的费用是经过 $C$ 条道路所花费的费用（即三人到 $P$ 的路径长度之和）。

---

样例

输入样例 1

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

输出样例 1

5 2
2 5
4 1
6 0

样例解释

树的结构：

    1
    |
    2
   / \
  3   4
      |
      5
      |
      6

1. 第一次聚会：三人位置 $4,5,6$。
   • 选择在 $5$ 聚会：$4\to5$ 距离 $1$，$5\to5$ 距离 $0$，$6\to5$ 距离 $1$，总费用 $2$。
   • 也可以选 $4$：费用 $0+1+2=3$，不如 $5$ 优。$5$ 是最优解。
2. 第二次聚会：三人位置 $6,3,1$。
   • 选择在 $2$ 聚会：$6\to2$ 距离 $3$（$6-5-4-2$），$3\to2$ 距离 $1$，$1\to2$ 距离 $1$，总费用 $5$。
3. 第三次聚会：三人位置 $2,4,4$。
   • 选择在 $4$ 聚会：$2\to4$ 距离 $1$，$4\to4$ 距离 $0$，$4\to4$ 距离 $0$，总费用 $1$。
4. 第四次聚会：三人位置 $6,6,6$。
   • 选择在 $6$ 聚会：总费用 $0$。

---

数据范围

• $1 \le N, M \le 5 \times 10^5$

时间限制：1000 ms
内存限制：524288 KB

---

提示

这是一个经典问题：树上三点最短路径汇聚点。

对于树上三个点 $a, b, c$，设 $lca(a,b)$ 为 $a$ 和 $b$ 的最近公共祖先，$lca(a,c)$、$lca(b,c)$ 同理。可以证明，三人到某点的路径长度之和最小的点 $P$ 是这三个 LCA 中深度最大的那个点（即最深的 LCA）。

设：

$$p_1 = lca(a,b),\quad p_2 = lca(a,c),\quad p_3 = lca(b,c)$$

令 $P$ 为 $p_1, p_2, p_3$ 中深度最大的节点，则 $P$ 就是最优聚会地点。

总费用 $C$ 的计算公式为：

$$C = dist(a,P) + dist(b,P) + dist(c,P)$$

其中 $dist(u,v)$ 是树上两点距离。

利用 $dist(u,v) = depth[u] + depth[v] - 2 \times depth[lca(u,v)]$ 可以简化计算。

实际上有更直接的公式：

$$C = depth[a] + depth[b] + depth[c] - depth[p_1] - depth[p_2] - depth[p_3]$$

这个公式可以通过对称性推导出来。

实现步骤：

1. 预处理树的深度 $depth$ 和倍增 LCA 所需信息（$fa[u][k]$）。
2. 对于每次询问 $a,b,c$：
   • 求出 $p_1 = lca(a,b)$，$p_2 = lca(a,c)$，$p_3 = lca(b,c)$。
   • 找出深度最大的那个作为 $P$。
   • 计算 $C = depth[a] + depth[b] + depth[c] - depth[p_1] - depth[p_2] - depth[p_3]$。
3. 输出 $P$ 和 $C$。

时间复杂度：预处理 $O(N \log N)$，每次询问 $O(\log N)$，总复杂度 $O((N+M)\log N)$，对于 $N,M \le 5\times 10^5$ 可以接受。注意输入输出使用快速方式（如 scanf/printf）。