{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Consider a tree T with N (1 \u0026lt;\u003d N \u0026lt;\u003d 20,000) nodes numbered 1...N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T.\r\u003cbr\u003eFor example, consider the tree:\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/03339b8159f12781609165773cf436da?v\u003d1715260528\"\u003e\u003c/center\u003e\r\u003cbr\u003eDeleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two.\r\u003cbr\u003e\r\u003cbr\u003eFor each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number.\r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input contains a single integer t (1 \u0026lt;\u003d t \u0026lt;\u003d 20), the number of test cases. The first line of each test case contains an integer N (1 \u0026lt;\u003d N \u0026lt;\u003d 20,000), the number of congruence. The next N-1 lines each contains two space-separated node numbers that are the endpoints of an edge in the tree. No edge will be listed twice, and all edges will be listed."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print a line containing two integers, the number of the node with minimum balance and the balance of that node."}},{"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\n7\r\n2 6\r\n1 2\r\n1 4\r\n4 5\r\n3 7\r\n3 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}