Removal Sequences

题意翻译

你有一张简单无向图，这张图上有 $n$ 个点 $m$ 条边，顶点编号为 $1 \sim n$，第 $i$ 个顶点的权值是 $a_i$。 你将删除一些顶点，特别的，定义删除顶点 $i$ 是合法的仅当 $i$ 的度数为 $a_i$，删除某个顶点后，与这个顶点相连的边也会被删除。 我们称一个移除序列 $p$ 是有效的当且仅当 $p_1,p_2,...p_n$ 是一个 $1 \sim n$ 的排列，且若依次删除 $p_1,p_2,...p_n$，每次删除都是合法的。 若存在两个合法的移除序列分别满足 $x$ 在 $y$ 前删除，$y$ 在 $x$ 前删除，且 $x<y$，则点对 $(x,y)$ 是美好的。 请统计所有“美好”的点对数量。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

题目描述

You are given a simple undirected graph, consisting of $ n $ vertices and $ m $ edges. The vertices are numbered from $ 1 $ to $ n $ . The $ i $ -th vertex has a value $ a_i $ written on it. You will be removing vertices from that graph. You are allowed to remove vertex $ i $ only if its degree is equal to $ a_i $ . When a vertex is removed, all edges incident to it are also removed, thus, decreasing the degree of adjacent non-removed vertices. A valid sequence of removals is a permutation $ p_1, p_2, \dots, p_n $ $ (1 \le p_i \le n) $ such that the $ i $ -th vertex to be removed is $ p_i $ , and every removal is allowed. A pair $ (x, y) $ of vertices is nice if there exist two valid sequences of removals such that $ x $ is removed before $ y $ in one of them and $ y $ is removed before $ x $ in the other one. Count the number of nice pairs $ (x, y) $ such that $ x < y $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains two integers $ n $ and $ m $ ( $ 1 \le n \le 10^5 $ ; $ 0 \le m \le \min(10^5, \frac{n \cdot (n - 1)}{2}) $ ) — the number of vertices and the number of edges of the graph. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le n - 1 $ ) — the degree requirements for each removal. Each of the next $ m $ lines contains two integers $ v $ and $ u $ ( $ 1 \le v, u \le n $ ; $ v \neq u $ ) — the description of an edge. The graph doesn't contain any self-loops or multiple edges. The sum of $ n $ over all testcases doesn't exceed $ 10^5 $ . The sum of $ m $ over all testcases doesn't exceed $ 10^5 $ . Additional constraint on the input: there always exists at least one valid sequence of removals.

输出格式

For each testcase, print a single integer — the number of nice pairs of vertices.

输入输出样例

输入样例 #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

题目大意：
你有一个简单无向图，包含n个顶点和m条边。顶点编号为1到n，第i个顶点有权值a_i。你可以删除一些顶点，但只有当顶点i的度数等于a_i时，删除才是合法的。删除一个顶点后，与该顶点相连的所有边也会被删除。一个有效的移除序列p是1到n的一个排列，使得按照p的顺序删除每个顶点都是合法的。如果存在两个有效的移除序列，其中一个序列中x在y之前被删除，另一个序列中y在x之前被删除，且x
输入输出数据格式：
输入格式：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和m（1≤n≤10^5；0≤m≤min(10^5, n×(n-1)/2)），分别表示顶点的数量和边的数量。
- 第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i≤n-1），表示每个顶点的度数要求。
- 接下来的m行，每行包含两个整数v和u（1≤v,u≤n；v≠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
```题目大意： 你有一个简单无向图，包含n个顶点和m条边。顶点编号为1到n，第i个顶点有权值a_i。你可以删除一些顶点，但只有当顶点i的度数等于a_i时，删除才是合法的。删除一个顶点后，与该顶点相连的所有边也会被删除。一个有效的移除序列p是1到n的一个排列，使得按照p的顺序删除每个顶点都是合法的。如果存在两个有效的移除序列，其中一个序列中x在y之前被删除，另一个序列中y在x之前被删除，且x