C. Chasing Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Colin and Eva are playing a chasing game on a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$.

In each game, Eva starts at node $$$S$$$ at time $$$0$$$ and moves toward her destination $$$T$$$, traversing one edge per second along the unique simple path from $$$S$$$ to $$$T$$$. More precisely, if this path is $$$p_0,p_1,\dots,p_k$$$, where $$$p_0=S$$$ and $$$p_k=T$$$, then Eva is at node $$$p_i$$$ at time $$$i$$$. After reaching $$$T$$$, she remains there until Colin catches her.

Colin starts at node $$$S'$$$ at time $$$0$$$. During each second, he may either remain at his current node or traverse one edge, arriving at the chosen node at the end of that second. Colin catches Eva when they occupy the same node at the same integer time.

The two players repeat the game independently for $$$q$$$ different choices of $$$S$$$, $$$T$$$, and $$$S'$$$. For each game, determine the earliest time at which Colin can catch Eva and the node where the catch occurs.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \times 10^5$$$, $$$1 \le q \le 2 \times 10^5$$$) — the number of nodes and the number of games.

Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$), denoting an edge between nodes $$$u_i$$$ and $$$v_i$$$. The given edges form a tree.

Each of the next $$$q$$$ lines contains three integers $$$S_i$$$, $$$T_i$$$, and $$$S'_i$$$ ($$$1 \le S_i,T_i,S'_i \le n$$$, $$$S_i \ne T_i$$$), denoting Eva's starting node, Eva's destination, and Colin's starting node, respectively, for the $$$i$$$-th game.

Output

For each game, output two integers $$$t_i$$$ and $$$p_i$$$: the earliest time $$$t_i$$$ at which Colin can catch Eva and the node $$$p_i$$$ where the catch occurs.

It can be proved that the value of $$$p_i$$$ is unique for every game.

Example
Input
5 3
1 2
1 3
3 4
3 5
4 1 2
3 5 1
5 2 4
Output
2 1
2 5
1 3