有一个无向图,有 $$$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”将被识别为肯定响应。
示例
输入 #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
输出 #1
YES YES NO YES NO
注意
在第一个测试用例中,您可以从顶点 $$$3$$$ 开始,击败其上的怪物,然后依次前往顶点 $$$2$$$、$$$1$$$,击败它们上的怪物。然后你返回顶点$$$3$$$,并前往顶点$$$4$$$,击败上面的怪物。
在第三个测试用例中,如果从顶点 $$$1$$$ 开始,则没有到顶点 $$$4$$$ 的路径。此外,如果从顶点 $$$4$$$ 开始,则没有到顶点 $$$1$$$、$$$2$$$ 和 $$$3$$$ 的路径。