Removal Sequences
Contest: Educational Codeforces Round 143 (Rated for Div. 2)
Difficulty rating: 2700
Tags: bitmasks, dfs and similar, graphs

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$$$.

Input format:
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.

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

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
1
0
4
0

Editorial:
Let's consider what the sequence of removals looks like in general. We will base some intuition on a fact that at least one valid sequence is guaranteed to exist.
Remove all vertices that have their degree correct from the start at once. There surely be such vertices, since a valid sequence would have to start with some of them.
Notice that there can't be any adjacent vertices among them. If there were, we wouldn't be able to remove such a pair regardless of the order we choose, since removing one of them makes another one's degree too low.
Now remove the vertices that just got their degrees correct from removing the first layer. Once again, these must exist (if the graph is not empty yet), because otherwise any valid sequence would get stuck.
Process until nothing is left.
This algorithm is basically a bfs, and you can implement it like one.
Note that each vertex becomes available to be removed only after a certain subset of its neighbours is removed. No matter what order you choose to remove the vertices in, these vertices will always be the same.
Huh, so for each vertex, some of its neighbours have to be removed before it, and the rest have to be removed after it (since otherwise, the degree of that vertex will become too low). That actually means that our graph is not as undirected as it seemed. We can direct each edge from a vertex that is removed before the other.
This makes a valid sequence of removals just a topological sort of that directed graph. So a pair is nice if there exist two topological orders such that $$$x$$$ and $$$y$$$ go one before another in them.
We can make a bold but perfectly reasonable guess about all nice pairs. A pair is nice if neither of $$$x$$$ and $$$y$$$ are reachable from each other.
The necessity of this condition is obvious. Let's show sufficiency.
Let's show the construction such that $$$x$$$ goes before $$$y$$$. To remove $$$x$$$, we first have to remove all vertices that have edges to $$$x$$$. To remove them, we have to remove vertices with edge to them. And so on. Basically, to remove $$$x$$$, we have to remove all vertices that are reachable from $$$x$$$ on the transposed directed graph. Since $$$x$$$ is not reachable from $$$y$$$, it doesn't have to be removed before $$$x$$$. So we can first remove all the required vertices, then remove $$$x$$$, then continue removing vertices until we are able to remove $$$y$$$.
By switching $$$x$$$ and $$$y$$$ in the description of that construction, we can obtain the construction for $$$y$$$ before $$$x$$$.
Thus, we reduced the problem to a rather well-known one. Calculate the number of reachable pairs of vertices in a directed graph.
As far as I know, it's not known to be solvable in sub-quadratic time. And we are not given a specific graph. Yes, it's obviously acyclic, but turns out every acyclic graph can be made into a test for this problem. You just have to make $$$d_v$$$ equal to the number of the outgoing edges for each $$$v$$$.
Somehow we are still given $$$10^5$$$ vertices and edges.
If you are more familiar with that problem, you might know that you can use bitset to solve it. In particular, let $$$\mathit{reach}[v]$$$ be a bitset such that $$$\mathit{reach}[v][u] = 1$$$ if $$$u$$$ if reachable from $$$v$$$. Then you can initialize $$$\mathit{reach}[v][v] = 1$$$ for all vertices and propagate the knowledge in reverse topological order by applying $$$\mathit{reach}[v] = \mathit{reach}[v] | \mathit{reach}[u]$$$ for all edges $$$(v, u)$$$.
Unfortunately, that requires $$$O(n^2)$$$ memory, and $$$10^{10}$$$ bits is over a gigabyte.
Let's use of my favorite tricks to make a solution with $$$O(n)$$$ memory and the same complexity. Man, I love that trick.
Process vertices in batches of $$$64$$$. Let's calculate which vertices can reach vertices from $$$1$$$ to $$$64$$$. The algorithm is basically the same. For each vertex, store a smaller bitset of size $$$64$$$ (also known as an unsigned long long). Initialize the bitset for $$$64$$$ vertices from the batch and propagate the same way for all $$$n$$$ vertices. Now just add up the number of ones in each bitset (__builtin_popcountll). Proceed to the next batch.
That makes it $$$\frac{n}{64}$$$ iterations of a $$$O(n + m)$$$ algorithm. This might require some constant optimizations. In particular, I suggest not to use dfs inside the iteration, since the recursion makes it really slow. You might iterate over a vertex in reverse topological order and its outgoing edges. Or, which is way faster, unroll that graph into a list of edges and iterate over it directly.