给你一个简单的无向图,由 $$$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