Вам дан неориентированный граф с \(n\) вершинами и \(m\) ребрами. Изначально для каждой вершины \(i\) существует монстр с опасностью \(a_{i}\) в этой вершине. Вы можете победить монстра с опасностью \(a_{i}\) тогда и только тогда, когда вы уже победили как минимум \(a_{i}\) других монстров.
Вы хотите победить всех монстров. Сначала вы выбираете некоторую вершину \(s\) и побеждаете монстра в этой вершине (поскольку вы еще не побеждали монстров, \(a_{s}\) должно быть равно \(0\)). Затем вы можете перемещаться в соседние вершины. Если вы хотите переместиться из вершины \(u\) в вершину \(v\), то должно выполняться следующее: либо монстр в вершине \(v\) уже побежден ранее, либо вы можете победить его сейчас. Во втором случае вы побеждаете монстра в вершине \(v\) и достигаете вершины \(v\). Вы можете проходить вершины и ребра любое количество раз.
Определите, сможете ли вы победить всех монстров или нет.
Выходные данные
Для каждого наборов входных данных выведите «YES», если вы можете победить всех монстров, и «NO» иначе.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных мы можем начать с вершины \(3\), победить монстра в ней, затем перейти в вершины \(2\), \(1\) в этом порядке, победив монстров в них. Затем вернуться к вершине \(3\) и пойти к вершине \(4\), победив в ней монстра.
В третьем наборе входных данных нет пути к вершине \(4\), если мы начинаем с вершины \(1\). Также нет пути к вершинам \(1\), \(2\), \(3\), если мы начнем с вершины \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 3
2 1 0 3
1 2
2 3
3 4
6 6
0 1 2 3 0 1
1 2
2 3
3 4
4 5
4 6
5 6
4 3
0 1 2 0
1 2
2 3
1 3
4 6
1 1 1 0
1 2
3 2
4 3
2 4
4 1
1 3
5 5
0 1 3 2 0
1 2
2 3
3 4
4 5
3 5
|
YES
YES
NO
YES
NO
|