{"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 is a city which is built like a tree.A terrorist wants to destroy the city\u0027s roads. But now he is alone, he can only destroy one road, then the city will be divided into two cities. Impression of the city is a number defined as the distance between the farthest two houses (As it relates to the fare).When the terrorist destroyed a road, he needs to spend some energy, assuming that the number is a.At the same time,he will get a number b which is maximum of the Impression of two cities. The terrorist wants to know which road to destroy so that the product of a and b will be minimized.You should find the road\u0027s id.\u003cbr\u003eNote that the length of each road is one.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains integer T(1\u0026lt;\u003dT\u0026lt;\u003d20), denote the number of the test cases.\u003cbr\u003eFor each test cases,the first line contains a integer n(1 \u0026lt; n \u0026lt;\u003d 100000);denote the number of the houses;\u003cbr\u003eEach of the following (n-1) lines contains third integers u,v,w, indicating there is a road between house u and houses v,and will cost terrorist w energy to destroy it.The id of these road is number from 1 to n-1.(1\u0026lt;\u003du\u0026lt;\u003dn , 1\u0026lt;\u003dv\u0026lt;\u003dn , 1\u0026lt;\u003dw\u0026lt;\u003d10000)"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output the case number first,and then output the id of the road which the terrorist should destroy.If the answer is not unique,output the smallest id."}},{"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\u003e2\r\n5\r\n4 5 1\r\n1 5 1\r\n2 1 1\r\n3 5 1\r\n5\r\n1 4 1\r\n1 3 1\r\n5 1 1\r\n2 5 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 2\r\nCase #2: 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}