A Dragon Lives

Time limit3sMemory limit128 MB

Summary

Given a day-by-day rain forecast on lakes and dry days when the dragon may empty one full lake, decide if overflow can always be avoided.

Level: Medium6 of 10
Topics: Greedy, Heap, Simulation
Solved: No attempts yet

Problem

Long, long ago, a dragon lived in a certain village. The village had several lakes, and at the very beginning every lake was full of water.

From time to time it rains in the village, and curiously the rain always falls on exactly one lake. When rain falls on an empty lake, the lake fills up again; but when rain falls on a lake that already holds water, it overflows and brings a terrible disaster upon the village.

On a day with no rain, the dragon may pick one lake and drink all of its water, emptying it. On a rainy day the dragon cannot drink, and it can never drink from a lake that is already empty. With its mysterious power the dragon knows exactly when and where every future rain will fall, so it can plan ahead.

Given the forecast for a number of days, determine whether the dragon can empty lakes so that no lake ever overflows.

Input

The first line contains the number of test cases Z.

For each test case, the first line contains two natural numbers n and m. n is the number of lakes and m is the number of days in the forecast. ( $1 \le n \le 10^6$ , $1 \le m \le 10^6$ )

The second line of each test case contains m integers $t_1, t_2, \dots, t_m$ . ( $0 \le t_i \le n$ ) If $t_i \ge 1$ , it rains on lake $t_i$ on day i; if $t_i = 0$ , no rain falls on day i and the dragon may drink all the water of one lake.

Output

For each test case, print one line: YES if the dragon can prevent every lake from overflowing, or NO otherwise.

Examples4

Example 1

Input

Expected output

NO
YES
NO
YES

Example 2
Input
```
1
1 2
0 1
```
Expected output
```
YES
```
Example 3
Input
```
1
1 1
1
```
Expected output
```
NO
```
Example 4
Input
```
1
3 3
0 0 0
```
Expected output
```
YES
```