Description

Original source: AHOI 2008

Y Island is renowned for its beautiful scenery, mild climate, and abundant resources. There are $N$ cities on Y Island, connected by $N-1$ roads. Each road links two cities. Fortunately, Little Coco can traverse all cities on the island via these roads. Interestingly, the cost of traveling through each road is the same.

Little Coco, Little Kaka, and Little YY often plan gatherings. For each gathering, they choose a city such that the total cost for all three to reach it is minimized.

Since they anticipate many such gatherings, selecting a location each time becomes tedious. Thus, they delegate this task to you. They will provide you with the map and their respective locations before each gathering, and you are to determine the optimal meeting point for each occasion.

Input Format

The first line contains two positive integers, $N$ and $M$, representing the number of cities and the number of gatherings, respectively.

The next $N-1$ lines each contain two positive integers $A$ and $B$, indicating a road between city $A$ and city $B$. Cities are numbered from $1$ to $N$.

The following $M$ lines each contain three positive integers, representing the locations of Little Coco, Little Kaka, and Little YY for a gathering.

Output Format

Output $M$ lines, each containing two numbers $P$ and $C$, separated by a space. For the $i$-th gathering, $P$ is the chosen city's number, and $C$ is the total cost, measured in the number of roads traveled.

Sample 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

5 2
2 5
4 1
6 0

Data Range and Hints

For $40\%$ of the data, $1\le N,M\le 2\times 10^3$;

For $100\%$ of the data, $1\le N,M\le 5\times 10^5$.