No submission language available for this problem.

Description

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \leq 10^5$, $0 \leq m \leq \min(10^5,\frac{n(n-1)}{2})$) — the number of club members and pairs of friends.

The second line of each test case contains $n$ integers $a_1,a_2, \dots,a_n$ ($0 \leq a_i \leq 10^4$) — the unhappiness value array.

Each of the next $m$ lines contains two integers $x$ and $y$ ($1 \leq x,y \leq n$, $x \neq y$) indicating that $x$ and $y$ are friends. Each unordered pair $(x,y)$ appears at most once in each test case.

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $10^5$.

Output

For each test case, print a line containing a single integer – the minimum possible unhappiness value of a valid party.

Samples

<div class="test-example-line test-example-line-even test-example-line-0">4</div><div class="test-example-line test-example-line-odd test-example-line-1">1 0</div><div class="test-example-line test-example-line-odd test-example-line-1">1</div><div class="test-example-line test-example-line-even test-example-line-2">3 1</div><div class="test-example-line test-example-line-even test-example-line-2">2 1 3</div><div class="test-example-line test-example-line-even test-example-line-2">1 3</div><div class="test-example-line test-example-line-odd test-example-line-3">5 5</div><div class="test-example-line test-example-line-odd test-example-line-3">1 2 3 4 5</div><div class="test-example-line test-example-line-odd test-example-line-3">1 2</div><div class="test-example-line test-example-line-odd test-example-line-3">1 3</div><div class="test-example-line test-example-line-odd test-example-line-3">1 4</div><div class="test-example-line test-example-line-odd test-example-line-3">1 5</div><div class="test-example-line test-example-line-odd test-example-line-3">2 3</div><div class="test-example-line test-example-line-even test-example-line-4">5 5</div><div class="test-example-line test-example-line-even test-example-line-4">1 1 1 1 1</div><div class="test-example-line test-example-line-even test-example-line-4">1 2</div><div class="test-example-line test-example-line-even test-example-line-4">2 3</div><div class="test-example-line test-example-line-even test-example-line-4">3 4</div><div class="test-example-line test-example-line-even test-example-line-4">4 5</div><div class="test-example-line test-example-line-even test-example-line-4">5 1</div><div class="test-example-line test-example-line-even test-example-line-4"></div>

0
2
3
2

Note

In the first test case, all members can be invited. So the unhappiness value is $0$.

In the second test case, the following options are possible:

• invite $1$ and $2$ ($0$ cakes eaten, unhappiness value equal to $3$);
• invite $2$ and $3$ ($0$ cakes eaten, unhappiness value equal to $2$);
• invite only $1$ ($0$ cakes eaten, unhappiness value equal to $4$);
• invite only $2$ ($0$ cakes eaten, unhappiness value equal to $5$);
• invite only $3$ ($0$ cakes eaten, unhappiness value equal to $3$);
• invite nobody ($0$ cakes eaten, unhappiness value equal to $6$).

The minimum unhappiness value is achieved by inviting $2$ and $3$.

In the third test case, inviting members $3,4,5$ generates a valid party with the minimum possible unhappiness value.