310290: CF1810E. Monsters

E. Monsterstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There is an undirected graph with $n$ vertices and $m$ edges. Initially, for each vertex $i$, there is a monster with danger $a_{i}$ on that vertex. For a monster with danger $a_{i}$, you can defeat it if and only if you have defeated at least $a_{i}$ other monsters before.

Now you want to defeat all the monsters. First, you choose some vertex $s$ and defeat the monster on that vertex (since you haven't defeated any monsters before, $a_{s}$ has to be $0$). Then, you can move through the edges. If you want to move from vertex $u$ to vertex $v$, then the following must hold: either the monster on vertex $v$ has been defeated before, or you can defeat it now. For the second case, you defeat the monster on vertex $v$ and reach vertex $v$.

You can pass the vertices and the edges any number of times. Determine whether you can defeat all the monsters or not.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Their description follows.

The first line of each test case contains two integers $n$, $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of vertices and edges in the graph respectively.

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($0 \le a_{i} \le n$) — the dangers of monsters on corresponding vertices.

For the following $m$ lines, each line contains two integers $u$, $v$ ($1 \le u, v \le n$), describing an edge connecting vertex $u$ and vertex $v$. It is guaranteed that there are no multi-edges or self-loops in the graph.

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.

Output

For each test case, output "YES" if you can defeat all the monsters, or "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

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

Output

YES
YES
NO
YES
NO

Note

In the first test case, you can start at vertex $3$ and defeat the monster on it, before you go to vertices $2$, $1$ in this order, defeating the monsters on them as well. Then you return to vertex $3$, and go to vertex $4$, defeating the monster on it.

In the third test case, there is no path to vertex $4$ if you start at vertex $1$. Also, there is no path to vertices $1$, $2$, and $3$ if you start at vertex $4$.

题目大意：
有一个包含n个顶点和m条边的无向图。初始时，每个顶点i上有一个危险值为a_i的怪物。要击败危险值为a_i的怪物，你必须先击败至少a_i个其他怪物。你想要击败所有怪物。首先，你选择一个顶点s并击败该顶点上的怪物（因为你之前没有击败任何怪物，所以a_s必须为0）。然后，你可以通过边移动。如果你想从顶点u移动到顶点v，则必须满足以下条件：要么顶点v上的怪物已经被击败，要么你现在可以击败它。对于第二种情况，你击败顶点v上的怪物并到达顶点v。你可以任意次数地经过顶点和边。判断是否可以击败所有怪物。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来的描述每个测试用例。
每个测试用例的第一行包含两个整数n、m（1≤n、m≤2×10^5）——图中顶点和边的数量。
每个测试用例的第二行包含n个整数a_1、a_2、…、a_n（0≤a_i≤n）——对应顶点上怪物的危险值。
接下来的m行，每行包含两个整数u、v（1≤u、v≤n），描述连接顶点u和顶点v的一条边。保证图中没有重边或自环。
保证所有测试用例的n之和和m之和不超过2×10^5。

输出数据格式：
对于每个测试用例，如果可以击败所有怪物，输出"YES"，否则输出"NO"。
输出答案时大小写不敏感。例如，"yEs"、"yes"、"Yes"和"YES"都会被识别为肯定回答。题目大意： 有一个包含n个顶点和m条边的无向图。初始时，每个顶点i上有一个危险值为a_i的怪物。要击败危险值为a_i的怪物，你必须先击败至少a_i个其他怪物。你想要击败所有怪物。首先，你选择一个顶点s并击败该顶点上的怪物（因为你之前没有击败任何怪物，所以a_s必须为0）。然后，你可以通过边移动。如果你想从顶点u移动到顶点v，则必须满足以下条件：要么顶点v上的怪物已经被击败，要么你现在可以击败它。对于第二种情况，你击败顶点v上的怪物并到达顶点v。你可以任意次数地经过顶点和边。判断是否可以击败所有怪物。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来的描述每个测试用例。 每个测试用例的第一行包含两个整数n、m（1≤n、m≤2×10^5）——图中顶点和边的数量。 每个测试用例的第二行包含n个整数a_1、a_2、…、a_n（0≤a_i≤n）——对应顶点上怪物的危险值。 接下来的m行，每行包含两个整数u、v（1≤u、v≤n），描述连接顶点u和顶点v的一条边。保证图中没有重边或自环。 保证所有测试用例的n之和和m之和不超过2×10^5。 输出数据格式： 对于每个测试用例，如果可以击败所有怪物，输出"YES"，否则输出"NO"。 输出答案时大小写不敏感。例如，"yEs"、"yes"、"Yes"和"YES"都会被识别为肯定回答。