Party

题意翻译

一个俱乐部计划举办一次聚会，并邀请 $n$ 名会员中的一些人。$n$ 名成员分别由数字 $1,2,...,n$ 表示。如果成员 $i$ 没有被邀请，团队将获得 $a_i$ 的不快乐值。 $n$ 名成员中有 $m$ 对好友。按照惯例，如果邀请了一对好友，他们会在聚会上分享蛋糕。被吃掉蛋糕的总数将等于两名成员都被邀请的好友的对数。 然而，俱乐部的烤箱一次只能烤两个蛋糕。因此，俱乐部要求吃掉的蛋糕总数是偶数。 聚会的最低的总不快乐值是多少，考虑到被吃掉的蛋糕总数为偶数的约束条件？

题目描述

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?

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

4
1 0
1
3 1
2 1 3
1 3
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
5 5
1 1 1 1 1
1 2
2 3
3 4
4 5
5 1

输出样例 #1

0
2
3
2

说明

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.

**题目大意：**
一个俱乐部计划举办一次聚会，并邀请部分会员。如果某个会员没有被邀请，俱乐部将获得其对应的不快乐值。会员间存在好友关系，如果一对好友都被邀请，他们会在聚会上分享一个蛋糕。由于烤箱一次只能烤两个蛋糕，所以要求吃掉的蛋糕总数为偶数。求聚会的最低总不快乐值，同时满足蛋糕总数为偶数的条件。

**输入数据格式：**
- 第一行包含一个整数 $ 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 $ 是好友。每对好友关系在测试用例中最多出现一次。

**输出数据格式：**
- 对于每个测试用例，输出一行，包含一个整数，表示聚会的最低总不快乐值。**题目大意：** 一个俱乐部计划举办一次聚会，并邀请部分会员。如果某个会员没有被邀请，俱乐部将获得其对应的不快乐值。会员间存在好友关系，如果一对好友都被邀请，他们会在聚会上分享一个蛋糕。由于烤箱一次只能烤两个蛋糕，所以要求吃掉的蛋糕总数为偶数。求聚会的最低总不快乐值，同时满足蛋糕总数为偶数的条件。 **输入数据格式：** - 第一行包含一个整数 $ 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 $ 是好友。每对好友关系在测试用例中最多出现一次。 **输出数据格式：** - 对于每个测试用例，输出一行，包含一个整数，表示聚会的最低总不快乐值。