It's already a hot April outside, and Polycarp decided that this is the perfect time to finally take down the spruce tree he set up several years ago. As he spent several hours walking around it, gathering his strength, he noticed something curious: the spruce is actually a tree(^{\text{∗}}) — and not just any tree, but one consisting of an odd number of vertices (n). Moreover, on (n-1) of the vertices hang Christmas ornaments, painted in exactly (\frac{n-1}{2}) distinct colors, with exactly two ornaments painted in each color. The remaining vertex, as tradition dictates, holds the tree's topper. At last, after several days of mental preparation, Polycarp began dismantling the spruce. First, he removed the topper and had already started taking apart some branches when suddenly a natural question struck him: how can he remove one of the tree's edges and rearrange the ornaments in such a way that the sum of the lengths of the simple paths between ornaments of the same color is as large as possible? In this problem, removing an edge from the tree is defined as follows: choose a pair of adjacent vertices (a) and (b) ((a < b)), then remove vertex (b) from the tree and reattach all of (b)'s adjacent vertices (except for (a)) directly to (a). Polycarp cannot continue dismantling his spruce until he gets an answer to this question. However, checking all possible options would take him several more years. Knowing your experience in competitive programming, he turned to you for help. But can you solve this dispute? (^{\text{∗}})A tree is a connected graph without cycles. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains an odd number (n) ((3 \le n < 2 \cdot 10^5)) — the number of vertices in the tree. The following (n-1) lines describe the tree, given