#P1711B. Party

Party

No submission language available for this problem.

Description

A club plans to hold a party and will invite some of its nn members. The nn members are identified by the numbers 1,2,,n1, 2, \dots, n. If member ii is not invited, the party will gain an unhappiness value of aia_i.

There are mm pairs of friends among the nn members. As per tradition, if both people from a friend pair are invited, they will share a cake at the party. The total number of cakes eaten will be equal to the number of pairs of friends such that both members have been invited.

However, the club's oven can only cook two cakes at a time. So, the club demands that the total number of cakes eaten is an even number.

What is the minimum possible total unhappiness value of the party, respecting the constraint that the total number of cakes eaten is even?

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

The first line of each test case contains two integers nn and mm (1n1051 \leq n \leq 10^5, 0mmin(105,n(n1)2)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 nn integers a1,a2,,ana_1,a_2, \dots,a_n (0ai1040 \leq a_i \leq 10^4) — the unhappiness value array.

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

It is guaranteed that both the sum of nn and the sum of mm over all test cases do not exceed 10510^5.

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

Input

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

The first line of each test case contains two integers nn and mm (1n1051 \leq n \leq 10^5, 0mmin(105,n(n1)2)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 nn integers a1,a2,,ana_1,a_2, \dots,a_n (0ai1040 \leq a_i \leq 10^4) — the unhappiness value array.

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

It is guaranteed that both the sum of nn and the sum of mm over all test cases do not exceed 10510^5.

Output

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

Samples

Sample Input 1

<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>

Sample Output 1

0
2
3
2

Note

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

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

  • invite 11 and 22 (00 cakes eaten, unhappiness value equal to 33);
  • invite 22 and 33 (00 cakes eaten, unhappiness value equal to 22);
  • invite only 11 (00 cakes eaten, unhappiness value equal to 44);
  • invite only 22 (00 cakes eaten, unhappiness value equal to 55);
  • invite only 33 (00 cakes eaten, unhappiness value equal to 33);
  • invite nobody (00 cakes eaten, unhappiness value equal to 66).
The minimum unhappiness value is achieved by inviting 22 and 33.

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