CF1795G Removal Sequences

给定一个简单无向图，包含 $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$。 输入保证至少存在一个合法的移除序列。

对于每个测试用例，输出一个整数，表示“好对”顶点对的数量。

由 ChatGPT 4.1 翻译