Migrated from Lutece 2720 守护最好的 0

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

0 国和 1 国是两个大国，但他们之间经常有矛盾，两国人民深受苦难之中。直到有一天，战争爆发了！

0 国可以看作是有 $n$ 个城市 $m$ 条双向道路形成的的简单无向连通图（不含重边和自环）。1 国决定先炸掉 0 国的一些城市来进行打击，而 0 国的防卫大臣知道了这件事，决定提前关闭一些道路来减少损失（也可以一条道路都不关闭）。关闭道路可以视为删除图中对应的双向边。

0 国的每个城市都有一个价值 $a_i$。1 国只会炸掉 0 国中形成奇数个城市的连通块。被炸掉的城市会对 0 国造成其对应价值的伤害；而未被炸掉的城市则会给予其对应价值的回复量。最终 0 国的生命值就等于回复量之和减去伤害之和。

现在，0 国的防卫大臣想知道国家的生命值最大可以是多少（可以是负数）。

Input

第一行一个正整数 $T$，表示有 $T$ 组数据。

对于每一组数据，第一行两个正整数 $n,m(2\le n \le 10^6, n-1\le m \le 10^6)$，分别表示 0 国的城市数和道路数。

第二行 $n$ 个正整数 $a_1,a_2,\ldots, a_n(1\le a_i \le 10^9)$，表示各个城市的价值。

接下来 $m$ 行，每行两个正整数 $x,y(1\le x , y\le n, x \ne y)$，表示 0 国有一条连接城市 $x$ 和 $y$ 的双向道路。

数据保证对于单个测试点，$\sum n \le 10^6, \sum m \le 2\cdot 10^6$

Output

对于每一组数据，输出一行一个整数，表示 0 国的最大生命值。

Samples

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

Note

第一组数据，唯一方案是删除道路 $(1,2), (1,3)$，答案就是 $2+3-1=4$.

第二组数据，一种方案是删除道路 $(2,4),(3,4)$，这样形成两个连通块 $[1,2,3,5],[4,6]$，每个连通块都是偶数个城市。

Resources

2022 UESTC ICPC Training for Graph