시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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 operation any number of times:

  • Remove all the cities with zero brightness from consideration.
  • Select an integer $k$ ($1\leq k\leq n$).
  • Select $k$ distinct unremoved 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$.

Sunset will always choose the maximum possible value of $k$ for each operation. Now Sunset is wondering what is the minimum number of operations he needs to do, please write a program to help him.

입력

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:

The first line 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 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 a 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.

출력

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

예제 입력 1

1
3 2
3 2 3
1 2
2 3

예제 출력 1

4