Задан простой неориентированный граф, состоящий из $$$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$$$.
Дополнительное ограничение на входные данные: всегда существует хотя бы одна корректная последовательность удалений.
На каждый набор входных данных выведите одно целое число — количество красивых пар вершин.
43 21 0 12 31 23 31 2 01 22 31 35 63 0 2 1 01 24 14 23 42 35 11 00
1 0 4 0
Название |
---|