CF1711B.Party

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

There are $m$ pairs of friends among the $n$ 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?

一个俱乐部计划举办一场聚会，并将邀请其 $n$ 名成员中的部分成员。这 $n$ 名成员编号为 $1, 2, \dots, n$。若未邀请成员 $i$，聚会将产生 $a_i$ 的不愉快值。

在 $n$ 名成员之间共有 $m$ 对朋友关系。按照传统，若某对朋友的两名成员均被邀请，则他们将在聚会上共食一块蛋糕。所吃蛋糕的总数等于双方均被邀请的朋友对的数量。

然而，俱乐部的烤箱一次最多只能烘烤两块蛋糕。因此，俱乐部要求所吃蛋糕的总数必须为偶数。

在满足“所吃蛋糕总数为偶数”这一约束的前提下，聚会可能达到的最小总不愉快值是多少？

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^5$，$0 \leq m \leq \min(10^5,\frac{n(n-1)}{2})$）—— 分别表示俱乐部成员人数和朋友对数。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2, \dots,a_n$（$0 \leq a_i \leq 10^4$）—— 表示不开心值数组。

接下来的 $m$ 行中，每行包含两个整数 $x$ 和 $y$（$1 \leq x,y \leq n$，$x \neq y$），表示 $x$ 和 $y$ 是朋友。在每个测试用例中，无序对 $(x,y)$ 至多出现一次。

保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $10^5$。

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

对于每个测试用例，输出一行，包含一个整数——有效聚会的最小可能不愉快值。

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.

在第一个测试用例中，可以邀请所有成员，因此不愉快值为 $0$。

在第二个测试用例中，以下方案是可行的：

• 邀请成员 $1$ 和 $2$（消耗 $0$ 块蛋糕，不愉快值为 $3$）；
• 邀请成员 $2$ 和 $3$（消耗 $0$ 块蛋糕，不愉快值为 $2$）；
• 仅邀请成员 $1$（消耗 $0$ 块蛋糕，不愉快值为 $4$）；
• 仅邀请成员 $2$（消耗 $0$ 块蛋糕，不愉快值为 $5$）；
• 仅邀请成员 $3$（消耗 $0$ 块蛋糕，不愉快值为 $3$）；
• 不邀请任何人（消耗 $0$ 块蛋糕，不愉快值为 $6$）。

最小的不愉快值通过邀请成员 $2$ 和 $3$ 实现。

在第三个测试用例中，邀请成员 $3,4,5$ 可构成一个合法的聚会，并达到可能的最小不愉快值。