Вам дан неориентированный граф с $$$n$$$ вершинами и $$$m$$$ ребрами. Изначально для каждой вершины $$$i$$$ существует монстр с опасностью $$$a_{i}$$$ в этой вершине. Вы можете победить монстра с опасностью $$$a_{i}$$$ тогда и только тогда, когда вы уже победили как минимум $$$a_{i}$$$ других монстров.
Вы хотите победить всех монстров. Сначала вы выбираете некоторую вершину $$$s$$$ и побеждаете монстра в этой вершине (поскольку вы еще не побеждали монстров, $$$a_{s}$$$ должно быть равно $$$0$$$). Затем вы можете перемещаться в соседние вершины. Если вы хотите переместиться из вершины $$$u$$$ в вершину $$$v$$$, то должно выполняться следующее: либо монстр в вершине $$$v$$$ уже побежден ранее, либо вы можете победить его сейчас. Во втором случае вы побеждаете монстра в вершине $$$v$$$ и достигаете вершины $$$v$$$. Вы можете проходить вершины и ребра любое количество раз.
Определите, сможете ли вы победить всех монстров или нет.
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следует их описание.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$0 \le a_{i} \le n$$$).
Следующие $$$m$$$ строк содержат по два целых числа $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$), описывающих ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что в графе нет кратных ребер и петель.
Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходят $$$2 \cdot 10^5$$$.
Для каждого наборов входных данных выведите «YES», если вы можете победить всех монстров, и «NO» иначе.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
54 32 1 0 31 22 33 46 60 1 2 3 0 11 22 33 44 54 65 64 30 1 2 01 22 31 34 61 1 1 01 23 24 32 44 11 35 50 1 3 2 01 22 33 44 53 5
YES YES NO YES NO
В первом наборе входных данных мы можем начать с вершины $$$3$$$, победить монстра в ней, затем перейти в вершины $$$2$$$, $$$1$$$ в этом порядке, победив монстров в них. Затем вернуться к вершине $$$3$$$ и пойти к вершине $$$4$$$, победив в ней монстра.
В третьем наборе входных данных нет пути к вершине $$$4$$$, если мы начинаем с вершины $$$1$$$. Также нет пути к вершинам $$$1$$$, $$$2$$$, $$$3$$$, если мы начнем с вершины $$$4$$$.
Название |
---|