每年圣诞老人都会给所有孩子送礼物。然而,每个国家都有自己的传统,并且这个过程以不同的方式进行。例如,在伯兰,你需要解决新年难题。
Polycarp 遇到了以下问题:给定一个大小为 $$$2 \times n$$$ 的网格带,其中的一些单元格被阻挡。您需要检查是否可以使用 $$$2 \times 1$$$ 和 $$$1 \times 2$$$ 瓷砖(多米诺骨牌)来平铺所有空闲单元。
例如,如果 $$$n = 5$$$ 并且条带如下所示(黑色单元格被阻挡):
然后就可以平铺了,比如使用两个垂直的和两个水平的平铺,如下图(不同的平铺用不同的颜色标记)。
如果 $$$n = 3$$$ 并且条带看起来像这样:
不可能平铺空闲单元。
波利卡普轻松解决了这个任务,并收到了他的新年礼物。你能解决吗?
输入
第一行包含一个整数 $$$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、yes、Yes 和 YES 将被识别为正)。
示例
输入 #1
3 5 2 2 2 1 4 3 2 2 1 2 3 6 4 2 1 2 3 2 4 2 6
输出 #1
YES NO NO
注意
声明中解释了前两个测试用例。
在第三个测试用例中,条带如下所示: