当前没有测试数据。

UCF is now the nation’s second largest university in student population.  To meet the demands

of a growing student body, the university is always constructing new buildings.  One of the

issues is the campus needs many new buildings but has limited space.  To help make room for

new buildings, a new restructuring method is being used!

Each day (until the end of restructuring) a building is selected for “reconstruction”. During

reconstruction, all buildings that are connected to the selected building and only to the selected

building are combined into (torn down and then added as new parts to) the selected building.

Every building has a given cost associated with applying this reconstruction operation; when a

building is selected and other buildings are combined with it, the cost associated with the

selected building is the cost for combining the selected group of buildings.

For example, in the building layout below, the building with cost 5 is selected in Day 1. The

building with cost 1 (crossed out in the picture in Day 1) is the only building connected to the

selected building and this building is connected to no other building. These two buildings are

combined and the cost of the operation is 5 (the cost of the selected building). In Day 2, the

building with cost 4 is selected (hence the cost 4 for combining) and in Day 3, the building with

cost 6 is selected. No more buildings can be selected after Day 3 since every building is

connected to more than one building. The total cost for this sequence of combinations is 

therefore 5+4+6= 15.

The Problem:

 

Given the building connections and the costs associated with refactoring the buildings, determine 

the minimum possible number of buildings that will be left when refactoring is complete, the 

minimum cost of achieving this minimum size and the number of ways to achieve this minimum 

cost with minimum size.  Two ways are considered different if on the i-th day the building being 

reconstructed is different or the number of days to complete the reconstruction differs.  Since the 

number of ways to reconstruct the university can be quite large, print the result modulo

1,000,000,007. 

 

 

 

Input

The first input line contains a positive integer, n, indicating the number of restructurings to 

perform.  Each restructuring will contain multiple lines. The first line contains two integers,

b (1 ≤ b ≤ 500) and c (1 ≤ c ≤ 2000), representing (respectively) the number of buildings and the 

number of connections between them.  The next line contains b integers, wi (1 ≤ wi ≤ 500), 

representing the cost of performing a reconstruction on the i-th selected building.  The next c lines 

each contain two integers, xi and yi (1 ≤ xi ≤ b, 1 ≤  yi ≤ b, xi ≠ yi), representing two identifiers for buildings that connect.  There will be at most one direct connection between any two buildings.

Also, every pair of buildings will be directly or indirectly connected.

Output

For each restructuring, first output the heading “Case #d: ”, where d is the test case number, 

starting with 1.  Then, print three integers separated by a single space: the minimum number of 

buildings left, the minimum cost for achieving this configuration, and the number of ways to 

achieve the minimum cost with minimum size. Follow the format illustrated in Sample Output.

Example

Input:
3
3 2
1 2 3
3 1
3 2
8 7
80 4 3 2 1 90 5 80
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 8
1 5 6 1 1 4 1 9
1 2
2 3
3 4
4 2
3 6
6 7
6 5
6 8
Output:

Case #1: 1 3 1
Case #2: 1 15 28
Case #3: 3 15 3