← 返回题目列表

Codeforces · 1810/E

E. 怪物

中文机器翻译题面 查看原题

有一个无向图,有 $$$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$$$ 的路径。