G. Последовательные удаления
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан простой неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Вершины пронумерованы от $$$1$$$ до $$$n$$$. На $$$i$$$-й вершине написано значение $$$a_i$$$.

Вы будете удалять вершины из этого графа. Вершину $$$i$$$ разрешается удалить только если ее степень равна $$$a_i$$$. Когда вершина удаляется, все инцидентные ребра также удаляются, соответственно, уменьшая степени соседних неудаленных вершин.

Корректная последовательность удалений — это такая перестановка $$$p_1, p_2, \dots, p_n$$$ $$$(1 \le p_i \le n)$$$, что вершина $$$p_i$$$ удаляется $$$i$$$-й по очереди, и каждое удаление разрешено.

Пара вершин $$$(x, y)$$$ называется красивой, если существуют две корректные последовательности удалений таких, что в одной $$$x$$$ удаляется раньше $$$y$$$, а в другой $$$y$$$ удаляется раньше $$$x$$$.

Посчитайте количество красивых пар $$$(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$$$.

Дополнительное ограничение на входные данные: всегда существует хотя бы одна корректная последовательность удалений.

Выходные данные

На каждый набор входных данных выведите одно целое число — количество красивых пар вершин.

Пример
Входные данные
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
0
4
0