度数和谐 2

题目描述

给定一张有 $N$ 个顶点、$M$ 条边的简单无向图 $G$，顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。另外给定一个正整数序列 $A=(A_1,A_2,\ldots,A_N)$。

如果 $G$ 的一个生成子图 $G'$ 满足以下条件，则称其为好图：

• 对于每个 $1 \le i \le N$，顶点 $i$ 在 $G'$ 中的度数不超过 $A_i$。

请求出好图中最多可能包含的边数。

本题有 $T$ 组测试数据，请分别求解。

输入格式

输入第一行为一个整数 $T$。

接下来依次给出 $T$ 组测试数据。每组测试数据的格式为：

N M
A_1 A_2 ... A_N
u_1 v_1
u_2 v_2
...
u_M v_M

输出格式

输出 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的答案。

3
4 4
2 2 1 1
1 2
1 3
1 4
2 3
6 7
3 3 1 1 1 1
1 2
1 3
1 5
2 3
2 5
3 4
5 6
10 12
1 2 2 1 1 1 1 1 1 1
1 2
1 5
1 8
2 3
2 4
3 4
5 6
5 7
6 7
8 9
8 10
9 10

3
3
5

样例 1 解释

第 $1$ 组数据中，只保留第 $1,3,4$ 条边得到的生成子图是好图。不存在包含 $4$ 条或更多条边的好图，所以答案为 $3$。

数据范围

对于所有测试数据，保证：

• $1 \le T \le 10$；
• $2 \le N \le 500$；
• $1 \le M \le \frac{N(N-1)}{2}$；
• $1 \le A_i \le N-1$；
• $\displaystyle \sum_{i=1}^N A_i \le 500$；
• $1 \le u_i < v_i \le N$；
• 当 $i \neq j$ 时，$(u_i,v_i) \neq (u_j,v_j)$；
• 所有测试数据的 $\displaystyle \left(\sum_{i=1}^N A_i\right)^3$ 之和不超过 $500^3$；
• 所有测试数据的 $M$ 之和不超过 $2 \times 10^5$；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。