In the course of history, there were two powerful nations on the Earth, known as Country A and Country B. Unfortunately, they did not get on well with each other and were often at odds with each other. The people of either country were not feeling easy because of the conflicts, large and small. And one day, war broke out between the two countries!

The map of the cities of Country A can be seen as a simple undirected connected graph of  roads and  cities (without multiple edges and self-loops). Country B plans to launch a strike and destroy the roads of Country A, but the plan is given away to the military minister of Country A. Therefore, the military minister of Country A decides to close some roads (maybe zero) in advance to reduce the damage.

Each city in Country A has an importance level . The importance level of a connected component is defined as follows: if the number of cities in the connected component is odd, then the importance level is the negative number of the total importance level of all cities; otherwise, it is the positive number of the total importance levels of all cities.

A component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the rest of the graph.

Now, suppose you are the military minister of Country A, and you should decide which roads to close in advance to maximize the total importance level of all components.

输入描述:

The first line contains an integer , indicating the number of test cases.

For each test case, the first line contains two integers , indicating the number of cities and roads in Country A.

The second line contains  integers , indicating the importance level of each city.
Each of the next  lines contains two integers , indicating that there is a road between City  and City  .

It is guaranteed that .

Due to the huge input, it is highly recommended to use faster I/O.

输出描述:

For each test case, print an integer in one line, indicating the maximal sum of the importance level of each component.

2
3 3
1 2 3
1 2
2 3
1 3
6 7
5 6 4 5 2 3
3 4
1 3
2 4
1 2
2 5
3 5
4 6

4
25

In the first case, deleting roads  is the only way.

In the second case, an optional way is to delete roads  and then get two components namely  and , both of which have an even number of cities.