There was a civil war between two factions in Skyrim, a province of the Empire on the continent of Tamriel. The Stormcloaks, led by Ulfric Stormcloak, are made up of Skyrim’s native Nord race. Their goal is an independent Skyrim free from Imperial interference. The Imperial Legion, led by General Tullius, is the military of the Empire that opposes the Stormcloaks and seeks to reunite and pacify the province.
The current target of Ulfric Stormcloak is to attack Whiterun City, which is under controlled by General Tullius. Near by this city there are N towers under the Empire’s control. There are N - 1 roads linking these towers, so soldiers can move from any tower to another one through these roads.
In military affairs, tactical depth means the longest path between two of all towers. Larger the tactical depth is, more stable these towers are.
Your mission, should you choose to accept it. In each turn, Ulfric tells you two roads. You need to figure out the tactical depth after destroying these two roads.
The first line of input contains an integer t which is the number of test cases. Then t test cases follow. For each test case, the first line contains two integers N(N ≤ 100000), representing the number of towers, and Q(Q ≤ 100000), represeting the number of queries.
In the next N - 1 lines, the i-th line describes the i-th road and contains three integers u, v and w (0 ≤ w ≤ 5000) corressponding to a path between u and v of length w.
In the next Q lines, each line contains two integers u and v representing that the u-th road and the v-th road would be destroyed in this turn. It is guaranteed that u $\neq$ v.
For each query, output the tactical depth.