CF1472F New Year's Puzzle

每年圣诞老人都会给所有孩子送礼物。然而，每个国家都有自己的传统，这一过程的方式也各不相同。例如，在 Berland，你需要解答新年谜题。 Polycarp 得到了如下问题：给定一个大小为 $2 \times n$ 的网格带，其中某些格子被阻塞。你需要判断是否可以用 $2 \times 1$ 和 $1 \times 2$ 的骨牌（多米诺骨牌）覆盖所有未被阻塞的格子。 例如，如果 $n = 5$，网格带如下（黑色格子为阻塞格）：  那么可以用两个竖直骨牌和两个水平骨牌进行覆盖，如下图所示（不同颜色表示不同的骨牌）。  如果 $n = 3$，网格带如下：  则无法覆盖所有未被阻塞的格子。 Polycarp 轻松地解决了这个问题并收到了新年礼物。你能解决它吗？

第一行包含一个整数 $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$）——表示被阻塞格子的行号和列号。保证所有被阻塞的格子互不相同，即 $(r_i, c_i) \ne (r_j, c_j), i \ne j$。 保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行： - 如果可以用 $2 \times 1$ 和 $1 \times 2$ 的骨牌覆盖所有未被阻塞的格子，输出 "YES"； - 否则输出 "NO"。 你可以以任意大小写输出 "YES" 和 "NO"（例如，yEs、yes、Yes 和 YES 都会被识别为肯定）。

前两个测试用例在题目描述中已经解释。 在第三个测试用例中，网格带如下：  很容易验证，未被阻塞的格子无法被骨牌覆盖。 由 ChatGPT 4.1 翻译