New Year's Puzzle
Contest: Codeforces Round 693 (Div. 3)
Difficulty rating: 2100
Tags: brute force, dp, graph matchings, greedy, sortings

Every year Santa Claus gives gifts to all children. However, each country has its own traditions, and this process takes place in different ways. For example, in Berland you need to solve the New Year's puzzle.

Polycarp got the following problem: given a grid strip of size $$$2 \times n$$$, some cells of it are blocked. You need to check if it is possible to tile all free cells using the $$$2 \times 1$$$ and $$$1 \times 2$$$ tiles (dominoes).

For example, if $$$n = 5$$$ and the strip looks like this (black cells are blocked):

Then it can be tiled, for example, using two vertical and two horizontal tiles, as in the picture below (different tiles are marked by different colors).

And if $$$n = 3$$$ and the strip looks like this:

It is impossible to tile free cells.

Polycarp easily solved this task and received his New Year's gift. Can you solve it?

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case is preceded by an empty line.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the length of the strip and the number of blocked cells on it.

Each of the next $$$m$$$ lines contains two integers $$$r_i, c_i$$$ ($$$1 \le r_i \le 2, 1 \le c_i \le n$$$) — numbers of rows and columns of blocked cells. It is guaranteed that all blocked cells are different, i.e. $$$(r_i, c_i) \ne (r_j, c_j), i \ne j$$$.

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

Output format:
For each test case, print on a separate line:

- "YES", if it is possible to tile all unblocked squares with the $$$2 \times 1$$$ and $$$1 \times 2$$$ tiles;
- "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first two test cases are explained in the statement.

In the third test case the strip looks like this:

Example input:
3

5 2
2 2
1 4

3 2
2 1
2 3

6 4
2 1
2 3
2 4
2 6

Example output:
YES
NO
NO

Editorial:
If the first column is empty, we can always cover it with a vertical tile:
• if the next column is also empty, then we will have to put either two vertical or two horizontal tiles, but they are obtained from each other by rotating;
• if the next column contains at least one blocked cell, then we have no other options but to cover the column with a vertical board.
If the first column is fully blocked, then we can just skip it.
Remove such columns from the beginning, reducing the problem. Now the first column contains one empty and one blocked cell. Obviously, in place of an empty cell, we will have to place a horizontal tile. If this did not work, then the tiling does not exist. Otherwise there are two cases:
• if the next column is empty, it will turn into a column with one occupied cell. Then we continue to put horizontal tiles;
• if the next column contains one blocked cell, then it becomes fully blocked and we return to the first step.
It turns out the following greedy algorithm, we sort all columns with at least one cell blocked (there are no more than $$$m$$$ such columns) by number. Now, if we see a column with one occupied cell, then the next one must also be with one occupied cell (we skipped the empty columns), but this cell must have a different color in the chess coloring (so that we can tile the space between them with horizontal boards. This check is easy to do after sorting the columns.