CF1472F.New Year's Puzzle

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?

每年，圣诞老人会向所有儿童赠送礼物。然而，每个国家都有自己的传统，因此这一过程以不同的方式进行。例如，在贝尔兰，你需要解开新年谜题。

波利卡普得到了如下问题：给定一个大小为 $2 \times n$ 的网格条带，其中部分格子被阻塞。你需要判断是否能用 $2 \times 1$ 和 $1 \times 2$ 的方块（即多米诺骨牌）完全覆盖所有未被阻塞的格子。

例如，若 $n = 5$，该条带如下图所示（黑色格子表示被阻塞）：

则可以实现覆盖，例如使用两个竖直放置和两个水平放置的多米诺骨牌，如下图所示（不同颜色代表不同的骨牌）：

而若 $n = 3$，该条带如下图所示：

则无法覆盖所有未被阻塞的格子。

波利卡普轻松解决了该问题，并收到了他的新年礼物。你也能解决它吗？

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$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例之前有一行空行。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^9$，$1 \le m \le 2 \cdot 10^5$）—— 条带的长度以及其上被阻塞的格子数量。

接下来的 $m$ 行中，每行包含两个整数 $r_i, c_i$（$1 \le r_i \le 2$，$1 \le c_i \le n$）—— 被阻塞格子所在的行号与列号。保证所有被阻塞的格子互不相同，即对任意 $i \ne j$，有 $(r_i, c_i) \ne (r_j, c_j)$。

保证所有测试用例的 $m$ 值之和不超过 $2 \cdot 10^5$。

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).

对于每个测试用例，在单独一行中输出：

• 如果可以用 $2 \times 1$ 和 $1 \times 2$ 的方块铺满所有未被阻挡的格子，则输出 "YES"；
• 否则输出 "NO"。

"YES" 和 "NO" 的大小写不限（例如，字符串 yEs、yes、Yes 和 YES 均被视为肯定回答）。

The first two test cases are explained in the statement.

In the third test case the strip looks like this:

It is easy to check that the unblocked squares on it can not be tiled.

前两个测试用例已在题目描述中说明。

在第三个测试用例中，条带如下所示：

容易验证，该条带上所有未被阻挡的方格无法被铺满。