Milad likes trees so much. He has a rooted tree with $n$ vertices each of which has some non-negative value $a_i$ $(1 ≤ i ≤ n)$. One day, he became interested to calculate the path value $sum_i$ $(1 ≤ i ≤ n)$ for each vertex from the root $1$. The path value of a vertex is the summation of values of all vertices in the path. Unfortunately, the next day he lost the values of all vertices. Not only he lost the values of all vertices, but also, he lost some random path values $sum_i$.
More formally, all that Milad has right now are his tree and some path values (all path values can be lost). So, for each of the lost path values $sum_i$ is equal to $-1$. Now, Milad needs your help to retrieve all the values of vertices, $a_i$ such that each of the lost path values can be replaced by some valid values and the summation of values of all vertices is minimum, or determine that he can’t retrieve from the given data.
Input starts with an integer $T (1 ≤ T ≤ 10)$, denoting the number of test cases.
Each case contains an integer $N (2 ≤ N ≤ 10^5)$, denoting the number of vertices in the tree.
The next line contains $N$ integers $sum_i$ $(-1 ≤ sum_i ≤ 10^9)$, denoting the path values for each vertex from the root $1$.
Each of the following $N - 1$ contains two integers $u$ and $v \; (1 \leq u, v \leq N)$ - denoting an edge of the tree.
For each test case, print a line "Case x: y" where $x$ is to be replaced by the test case number and $y$ is to be replaced by the minimum total summation of values of all vertices or $-1$ if you can’t determine the values.
| Input | Output |
|---|---|
2 3 4 -1 3 1 2 2 3 4 1 -1 -1 -1 1 2 1 3 1 4 | Case 1: -1 Case 2: 1 |