Escape Room Exploration

Alice and Bob are testing a new escape room. The dungeon is composed of n rooms connected by exactly n-1 corridors, forming a tree (i.e. it is possible to travel between any two rooms).

Two special rooms exist in the dungeon. One room contains a protective idol called the "helix key" and a different room contains a dangerous "dome trap." The trap, if entered before collecting the key, will trap the player in the dungeon forever. The player’s starting room is guaranteed to be different from the room with the key and the room with the trap.

There are q scenarios. In the i^th scenario, the player starts at room s_i, the key is in room k_i, and the trap is in room t_i. The player must explore the entire dungeon (i.e. visit every room) with the additional constraint that the trap room is visited only after the key has been collected.

It turns out that an optimal strategy is to plan a route that starts at s_i and ends at the trap room t_i. In any tree, the minimum route to cover all nodes starting at a given vertex and ending at another vertex is equal to

$$\text{Cost} = 2(n-1) - d(s,t),$$

where \(d(s,t)\) is the distance (i.e. number of corridors) on the unique path between rooms \(s\) and \(t\). Since the route can be re-arranged to ensure that the key is grabbed before the trap is ever visited (even if the key is not on the unique path from \(s\) to \(t\)), the answer for each scenario is given by the above formula.

Your task is to compute this minimum amount of time (i.e. the total cost) for each scenario.

inputFormat

The first line contains two integers n and q (\(2 \le n \le 10^5\), \(1 \le q \le 10^5\)) — the number of rooms in the dungeon and the number of scenarios.

Each of the next n-1 lines contains two integers u and v (\(1 \le u,v \le n\)), indicating that there is a corridor connecting room u and room v.

Each of the next q lines contains three integers s, k, and t (\(1 \le s,k,t \le n\) with \(s \neq k\) and \(s \neq t\) and \(k \neq t\)), representing the starting room, the room with the key, and the room with the trap, respectively.

outputFormat

For each scenario, output a single integer — the minimum amount of time needed to explore the entire dungeon while collecting the key before triggering the trap. The answer for a scenario is computed by

$$2(n-1) - d(s,t),$$

where \(d(s,t)\) is the distance between room \(s\) and room \(t\) in the dungeon.

sample

3 2
1 2
2 3
1 3 2
1 2 3

3
2

</p>