Colin and Eva are playing a chasing game on a given tree with nodes, indexed from to .

Colin knows that Eva will start from node at time , and move towards her destination node at the speed of 1 edge per second. (i.e. Assuming that the path from to is , then Eva will arrive at node at time ) After arriving at node , Eva will stay still there until she is caught by Colin.

Now Colin wants to chase Eva. At time , Colin is at node ; every second Colin can choose to stay still at the current node or to move once along the edge connected to the current node, and arrive at the other node of this edge at the end of this second.

Colin wants to chase Eva as soon as possible. Can you tell him what's the minimum time that Colin and Eva will be at the same node.

Colin and Eva will play this game times, you need to tell Colin the minimum time for every game, and the corresponding index of the node.

The first line contains two integers  , representing the number of nodes and the times Eva and Colin play the chasing game for.

For the following  lines, each line contains two integers  , representing that there is an edge connecting node  and node 
 . It's guaranteed that the given edges form a tree.

For the following  lines, each line contains three integers  , representing the start point for Eva, the end point for Eva, and the start point for Colin.

Output  lines.

The -th line contains two integers  , representing the minimum time that Colin and Eva will be at the same node is  , and the index of this node is  .

It can be proved there is only one possible value of  for each game.

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