CF1711B Party

一个俱乐部计划举办一场聚会，并将邀请其 $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$。

对于每个测试用例，输出一行一个整数，表示满足条件的最小不开心值。

在第一个测试用例中，可以邀请所有成员，因此不开心值为 $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$ 可以得到最小的不开心值并满足条件。 由 ChatGPT 4.1 翻译