You are given a rooted tree consisting of n vertices numbered from 1 to n, and the root is vertex 1.
Vertex i has a natural number weight ai, and no two different vertexes have the same weight.
Define bu=MEX x ∣ ∃v∈subtree(u),x=av}.
Unfortunately, ai are not given. Please find out the maximum possible ∑i=1nbi.
TheMEX of a set is the minimum non-negative integer that doesn't belong to the set.
The first line contains one integer T(1≤T≤10), indicating the number of test cases.
For each test case:
The first line contains one integer n(1≤n≤5⋅105), indicating the number of nodes.
In the following n-1 lines, each line contains two interger u,v(1≤u,v≤n), indicating an edge (u,v) of the tree.
A guarantee is that forming trees.
3
5
1 2
3 2
1 5
4 1
3
1 2
2 3
18
6
1