题目描述

小 Z 和小 Y 正在一棵无根树上玩追逐游戏。树由 $n$ 个节点构成，编号分别是 $1,2,\dots,n$ 。

已知小 Z 会在 $0$ 秒时从 $S$ 号节点出发，以每秒一条边的速度前往 $T$ 号节点，且小 Z 会沿着这两点之间的最短路移动。形式化的，假设树上从 $S$ 到 $T$ 的最短路径经过的节点编号依次是 $p_0,p_1,\dots,p_k$，其中 $p_0=S,p_k=T$，那么小 Z 在第 $i$ 秒时会位于 $p_i$ 号节点。在小 Z 到达 $T$ 号节点后，他会一直停在 $T$ 号点，直到他被小 Y 抓住。

小 Y 会在 $0$ 秒时从 $S'$ 号节点出发，且小 Y 完全了解小 Z 的行动路线。每秒小 Y 可以选择沿着与当前节点连接的一条边移动，或者停在当前节点不动。小 Y 会选择最优的方式移动，使他能够尽早抓住小 Z 。 我们称小 Y 在 $t$ 秒时抓住了小 $Z$ ，当且仅当在第 $t$ 秒时，小 Y 和小 Z 恰好在同一个节点。注意小 Y 只能在节点上抓到小 Z，而不能在边上抓住小 Z。

他们一共进行了 $q$ 次追逐游戏，对于每次游戏，如果小 Y 都使用最优策略，请你计算小 Y 最早什么时刻抓住小 Z，以及在哪个节点抓住小 Z。可以证明，在最优策略下，题目所求的时间和节点都唯一。

输入格式

从 chase.in 文件读入数据。

第一行两个整数 $n,q$ 。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i\ (1\le u_i,v_i\le n, u_i\not = v_i)$，代表树上的一条边。保证输入的所有边构成了一棵树。

接下来 $q$ 行，每行三个整数 $S_i,T_i,S_i'(1\le S_i,T_i,S_i'\le n, S_i\not = T_i)$，代表小 Z 的起点，小 Z 的终点，小 Y 的起点。

输出格式

输出到 chase.out 文件。

输出 $q$ 行，每行两个整数 $t_i,p_i$，代表第 $i$ 次游戏小 Y 最早在 $t_i$ 秒时抓住小 Z，相应的节点是 $p_i$ 号节点。

样例

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

2 1 
2 5 
1 3

样例 2

点击链接 ex_chase2.in 和 ex_chase2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有数据，$1 \leq n,q\leq 2\times 10^5$。