| Codeforces Round 693 (Div. 3) |
|---|
| Закончено |
Каждый год Дед Мороз дарит подарки всем детям. Однако в каждой стране есть свои традиции, и этот процесс происходит по разному. Например в Берляндии нужно решить новогоднюю головоломку.
Поликарпу досталась следующая задача: дана клетчатая полоска размером $$$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$$$.
Для каждого набора входных данных в отдельной строке выведите:
- «YES», если можно ли замостить все незаблокированные клетки с помощью дощечек $$$2 \times 1$$$ и $$$1 \times 2$$$;
- «NO» в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).
3 5 2 2 2 1 4 3 2 2 1 2 3 6 4 2 1 2 3 2 4 2 6
YES NO NO
Первые два набора входных данных разобраны в условии.
В третьем наборе входных данных полоска выглядит следующим образом
