5411: Defend Your Country

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 T ,indicating the number of test cases.

For each test case, the first line contains two integers n,m(2≤n≤10⁶,1≤m≤10⁶,m≥n-1) indicating the number of cities and roads in Country A.

The second line contains  integers a1,a2…,an(1≤ai≤10⁹), indicating the importance level of each city.

Each of the next m lines contains two integers x,y, indicating that there is a road between City x and City y. 

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 (1,2) , (1,3) is the only way.

In the second case, an optional way is to delete roads (2,4) , (3,4) and then get two components namely  (1,2,3,5) and (4,6) , both of which have an even number of cities.