← 返回题目列表

Codeforces · 1795/G

G. 拆卸顺序

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

给你一个简单的无向图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。顶点编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个顶点上写有值 $$$a_i$$$。

您将从该图中删除顶点。仅当顶点 $$$i$$$ 的度数等于 $$$a_i$$$ 时,才允许删除该顶点。当一个顶点被移除时,所有与其相关的边也被移除,从而减少了相邻未移除顶点的度数。

有效的删除序列是一个排列 $$$p_1, p_2, \dots, p_n$$$ $$$(1 \le p_i \le n)$$$ 使得要删除的第 $$$i$$$ 个顶点是 $$$p_i$$$,并且允许每次删除。

如果存在两个有效的删除序列,使得 $$$x$$$ 在其中一个中的 $$$y$$$ 之前删除,而 $$$y$$$ 在另一个中的 $$$x$$$ 之前删除,那么一对 $$$(x, y)$$$ 顶点就很好。

计算 $$$(x, y)$$$ 的好对的数量,使得 $$$x < y$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$0 \le m \le \min(10^5, \frac{n \cdot (n - 1)}{2})$$$) — 图的顶点数和边数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n - 1$$$) - 每次移除的度数要求。

接下来的 $$$m$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) - 边的描述。

该图不包含任何自环或多重边。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

对输入的附加约束:始终存在至少一个有效的移除序列。

输出

对于每个测试用例,打印一个整数——好的顶点对的数量。

示例

输入 #1

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

输出 #1

1
0
4
0