{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nMarjar University is a beautiful and peaceful place. There are \u003cvar\u003eN\u003c/var\u003e buildings and \u003cvar\u003eN\u003c/var\u003e - 1 bidirectional roads in the campus. These buildings are connected by roads in such a way that there is exactly one path between any two buildings. By coincidence, the length of each road is 1 unit.\n\u003c/p\u003e\n\n\u003cp\u003e\nTo ensure the campus security, Edward, the headmaster of Marjar University, plans to setup two fire stations in two different buildings so that firefighters are able to arrive at the scene of the fire as soon as possible whenever fires occur. That means the longest distance between a building and its nearest fire station should be as short as possible.\n\u003c/p\u003e\n\n\u003cp\u003e\nAs a clever and diligent student in Marjar University, you are asked to write a program to complete the plan. Please find out two proper buildings to setup the fire stations.\n\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\n\u003cp\u003eThere are multiple test cases. The first line of input contains an integer \u003cvar\u003eT\u003c/var\u003e indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003e\nThe first line contains an integer \u003cvar\u003eN\u003c/var\u003e (2 \u0026lt;\u003d \u003cvar\u003eN\u003c/var\u003e \u0026lt;\u003d 200000).\n\u003c/p\u003e\n\n\u003cp\u003e\nFor the next \u003cvar\u003eN\u003c/var\u003e - 1 lines, each line contains two integers \u003cvar\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e. That means there is a road connecting building \u003cvar\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and building \u003cvar\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (indexes are 1-based).\n\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\n\u003cp\u003e\nFor each test case, output three integers. The first one is the minimal longest distance between a building and its nearest fire station. The next two integers are the indexes of the two buildings selected to build the fire stations.\n\u003c/p\u003e\n\n\u003cp\u003e\nIf there are multiple solutions, any one will be acceptable.\n\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\n4\n1 2\n1 3\n1 4\n5\n1 2\n2 3\n3 4\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 1 2\n1 2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}