{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThere 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.\u003cbr\u003eThe 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.\u003cbr\u003eIn military affairs, tactical depth means the longest path between two of all towers. Larger the tactical depth is, more stable these towers are.\u003cbr\u003eYour 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.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"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.\u003cbr\u003eIn 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.\u003cbr\u003eIn 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.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each query, output the tactical depth.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n8 3\r\n2 1 7\r\n3 1 7\r\n4 2 5\r\n5 2 6\r\n4 6 3\r\n7 2 8\r\n1 8 2\r\n4 6\r\n2 3\r\n5 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e22\r\n17\r\n20\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}