Total Eclipse

Problem Description

There are $n$ cities and $m$ bidirectional roads in Byteland. These cities are labeled by $1,2,\dots,n$, the brightness of the $i$-th city is $b_i$. Magician Sunset wants to play a joke on Byteland by making a total eclipse such that the brightness of every city becomes zero. Sunset can do the following operations for arbitrary number of times: · Select an integer $k$ ($1\leq k\leq n$). · Select $k$ distinct cities $c_1,c_2,\dots,c_k$ ($1\leq c_i\leq n$) such that they are connected with each other. In other words, for every pair of distinct selected cities $c_i$ and $c_j$ $(1\leq i<j\leq k)$, if you are at city $c_i$, you can reach city $c_j$ without visiting cities not in $\{c_1,c_2,\dots,c_k\}$. · For every selected city $c_i$ ($1\leq i\leq k$), decrease $b_{c_i}$ by $1$. Note that Sunset will always choose $k$ with the maximum possible value. Now Sunset is wondering what is the minimum number of operations he needs to do, please write a program to help him.

Input

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each case, the first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 100\,000$, $1\leq m\leq 200\,000$), denoting the number of cities and the number of roads. The second line of the input contains $n$ integers $b_1,b_2,\dots,b_n$ ($1\leq b_i\leq 10^9$), denoting the brightness of each city. Each of the following $m$ lines contains two integers $u_i$ and $v_i$ ($1\leq u_i,v_i\leq n,u_i\neq v_i$), denoting an bidirectional road between the $u_i$-th city and the $v_i$-th city. Note that there may be multiple roads between the same pair of cities.

Output

For each test case, output a single line containing an integer, the minimum number of operations.

Sample Input

1
3 2
3 2 3
1 2
2 3

Sample Output

4

Source

2020 Multi-University Training Contest 2