Problem D
Lost Trams

A tree of tram lines (each line starts and ends at a leaf node). Queries indicate trams have taken a wrong route and must head to the nearest terminus (leaf node) to turn around. Calculate the total extra distance traveled by the trams.

In the city of Tramville, trams are the best way to get around. Unfortunately, the tram network in Tramville has some limitations; for example, trams cannot reverse because they only have driver’s cabins at one end. This is particularly problematic because the tram network forms a tree, meaning there are no cycles in the network. To avoid trams getting stranded, Tramville has built turning loops at all leaf nodes, allowing trams to turn around there. Since leaf nodes are the only locations where a tram can turn around, all terminus stations of the tram network are located at leaf nodes.

Tramville’s passengers aren’t always attentive to where the tram is heading, so when a tram takes a wrong route, it can be noticed anywhere between the error and the incorrect terminus. However, once passengers notice the tram has taken the wrong route, they always file a formal complaint with BestTransit and loudly notify everyone else onboard, ensuring no one else files another complaint. This commotion makes the driver alert, guaranteeing the tram turns around at the nearest possible terminus stations.

BestTransit, responsible for tram operations, has just received this year’s error report. There are a total of $Q$ complaints from passengers about trams going the wrong way. Each complaint specifies the station where the error was noticed and the terminus stations between which the tram was initially traveling before the error. Can you help BestTransit calculate how much extra distance each tram had to travel due to the errors?

Input

The first line contains two integers $N$ and $Q$ ($2 \leq N \leq 2 \cdot 10^5, 1 \leq Q \leq 10^5$), the number of stations and the number of complaints.

Then follow $N-1$ lines, each with two integers $a$ and $b$, indicating that stations $a$ and $b$ are directly connected.

Finally, there are $Q$ lines containing three integers each: $n, s_1, s_2$, indicating the station where the passenger noticed the error and the terminus stations the tram was originally traveling between. It’s guaranteed that the tram was moving away from its correct route when the complaint was filed, meaning it could continue from station $n$ in any direction except the one it came from (unless at a terminus, where it can only return). All stations are numbered between $1$ and $N$.

Output

Output $Q$ lines, each containing a single integer representing the extra distance traveled by the tram for each complaint, in the order they appear in the input.

Scoring

Your solution will be tested on multiple test groups. To earn points for a group, you must pass all test cases in that group.

Explanation

In the second sample case, the tram initially travels between nodes $1$ and $4$ but ends up at node $5$, implying it took a wrong turn at node $2$. The nearest terminus from node $5$ is node $6$. The distance between node $2$ and node $6$ is two, meaning the tram travels an extra $4$ stations. The second tram travels between nodes $4$ and $6$ but ends up at node $7$, indicating a wrong turn at node $3$. Since node $7$ is a terminus, we calculate the distance between nodes $3$ and $7$, which is $1$, resulting in an extra travel distance of $2$ stations.
In the third sample case, the tram traveling between nodes $1$ and $4$ ends up at node $6$, indicating a wrong turn at node $2$. The nearest terminus is node $9$, and the distance from node $2$ to node $9$ is $4$, resulting in an extra travel distance of $8$ stations.

Figure 1: The tram network in sample $3$.

9 1
1 2
2 3
3 4
2 5
2 6
6 7
7 8
8 9
6 1 4

8

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

4
2

10 1
1 2
2 3
3 4
2 5
5 6
5 7
7 8
8 9
9 10
7 1 4

10