#216730. [GKS 2019 #F] Spectating Villages

The countryside of Kickstartia consists of villages (labelled from 1 to ), connected by bidirectional roads (labelled from 1 to ). The i-th road connects village to village . Each road connects exactly two villages, and no two roads connect the same two villages. Furthermore, there is exactly one sequence of roads that connects any two villages in Kickstartia.

Some villages are more beautiful than others. The i-th village has a beauty value of . Note that it is possible for a village to have a negative beauty value!

You are going to build lighthouses in some of the villages. A village is illuminated if there is a lighthouse built in it, or there is a lighthouse built in a village that is directly connected to it by a road.

You may build as many or as few (even zero) lighthouses as you like. What is the maximum possible sum of beauty values of illuminated villages you can obtain?

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing the integer , the number of villages. The second line contains integers. The i-th of these is , the beauty value of the i-th village.

Then, lines follow. The i-th line gives and , indicating the i-th road connects village to village .

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum possible sum of beauty values of illuminated villages you can obtain.

样例输入 1

3
9
-10 4 -10 8 20 30 -2 -3 7
1 4
2 4
4 3
9 4
9 8
7 5
6 7
7 9
4
-2 20 20 20
1 2
1 3
1 4
5
-5 -10 8 -7 -2
5 4
4 3
3 2
2 1

样例输出 1

Case #1: 67
Case #2: 58
Case #3: 0

In Sample Case #1, you can place a lighthouse in villages 2 and 7. This illuminates villages 2, 4, 5, 6, 7 and 9, for a total beauty of . There are other possible ways to place lighthouses to achieve this total beauty.

In Sample Case #2, you can place a lighthouse in villages 1, 2 and 3. This illuminates villages 1, 2, 3 and 4, for a total beauty of . There are other possible ways to place lighthouses to achieve this total beauty.

In Sample Case #3, the best you can do is to place no lighthouses at all! This illuminates no villages for a total beauty of 0.

Limits

.

.

for all i.

for all i.

for all i.

for all .

There is exactly one sequence of roads connecting every pair of villages.

Test set 1 (Visible)

.

Test set 2 (Hidden)

.