A15677 | Removal Sequences

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.