Description

On Happy Island there is a fun game called "Emergency Assembly." There are $n$ waiting points scattered around the island, connected by $n-1$ roads. Each road connects two waiting points, and by these roads one can reach all waiting points. Moving along a road from one point to another costs one game coin.

Players participate in teams of three. At the start, all players are arbitrarily located at various waiting points (each point may have multiple players waiting at the same time). Every player carries enough game coins (to pay the road costs), a map (showing the road connections between the waiting points), and a communicator (to contact their teammates). When the assembly signal sounds, teammates quickly contact each other, learn the waiting points of all members in their team, and then promptly choose one meeting point among the $n$ waiting points. All team members will gather at that meeting point. The team with the smallest total cost of gathering will be the winner.

Xiao Keke and friends invite you to join the game, and you are in charge of choosing the meeting point. Can you smartly complete this task and help Xiao Keke win?

Input Format

The first line contains two positive integers $n$ and $m$, denoting the number of waiting points (waiting points are numbered from $1$ to $n$) and the number of gatherings that must be completed to win a prize.

Then follow $n-1$ lines. Each of these lines contains two positive integers $a, b$, indicating there is a road between waiting point $a$ and waiting point $b$.

Then follow $m$ lines. Each line contains three positive integers $x, y, z$, indicating, before a particular gathering, the waiting points occupied by Xiao Keke, Xiao Keke’s friend, and you, respectively.

Output Format

Output $m$ lines. Each line should contain two integers $p, c$ separated by a space. The $i$-th line indicates that for the $i$-th gathering, the chosen meeting point is the waiting point numbered $p$, and the total cost of gathering is $c$ game coins.

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

5 2
2 5
4 1
6 0

Hint

• For $40\%$ of the testdata, $n \leq 2 \times 10^3$, $m \leq 2 \times 10^3$.
• For $100\%$ of the testdata, $1 \leq x, y, z \leq n \leq 5 \times 10^5$, $1 \leq m \leq 5 \times 10^5$.

Translated by ChatGPT 5