← 返回题目列表

Codeforces · 1711/B

B. 聚会

中文机器翻译题面 查看原题

某俱乐部计划举办一场聚会,并将邀请一些 $$$n$$$ 会员。 $$$n$$$ 成员由数字 $$$1, 2, \dots, n$$$ 标识。如果成员$$$i$$$没有被邀请,该队伍将获得$$$a_i$$$的不快乐值。

$$$n$$$ 成员中有$$$m$$$ 对朋友。按照传统,如果一对朋友都受到邀请,他们将在聚会上分享蛋糕。吃掉的蛋糕总数将等于朋友对的数量,这样两个成员都被邀请了。

不过,俱乐部的烤箱一次只能烤两个蛋糕。所以,俱乐部要求吃掉的蛋糕总数是偶数。

在吃蛋糕总数为偶数的约束下,该方的最小可能总不快乐值是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,打印一行包含单个整数 - 有效方的最小可能不快乐值。

示例

输入 #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

注意

在第一个测试用例中,可以邀请所有成员。所以不快乐值是$$$0$$$。

在第二个测试用例中,可以使用以下选项:

- 邀请$$$1$$$和$$$2$$$(吃了$$$0$$$蛋糕,不快乐值等于$$$3$$$);
- 邀请$$$2$$$和$$$3$$$(吃了$$$0$$$蛋糕,不快乐值等于$$$2$$$);
- 仅邀请$$$1$$$(吃了$$$0$$$蛋糕,不快乐值等于$$$4$$$);
- 仅邀请$$$2$$$(吃了$$$0$$$蛋糕,不快乐值等于$$$5$$$);
- 仅邀请$$$3$$$(吃了$$$0$$$蛋糕,不快乐值等于$$$3$$$);
- 不邀请任何人(吃了$$$0$$$蛋糕,不快乐值等于$$$6$$$)。

在第三个测试用例中,邀请成员 $$$3,4,5$$$ 生成一个具有最小可能不快乐值的有效政党。