F. Космическое разбиение
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Когда артефакт находится у тебя в руках, ткань реальности уступает место своему истинному хозяину — мужчине из Флориды.

Полимино является связной$$$^{\text{∗}}$$$ фигурой, построенной путем присоединения одного или нескольких равных квадратов $$$1 \times 1$$$ сторона к стороне. Полимино является выпуклым, если для любых двух квадратов в полимино, которые находятся в одной строке или одном столбце, все квадраты между ними также являются частью полимино. Ниже приведены четыре полимино, только первое и второе из которых выпуклые.

Вам дано выпуклое полимино с $$$n$$$ строками и четной площадью. Для каждой строки $$$i$$$ от $$$1$$$ до $$$n$$$ единичные квадраты от столбца $$$l_i$$$ до столбца $$$r_i$$$ являются частью полимино. Другими словами, в $$$i$$$-й строке находится $$$r_i - l_i + 1$$$ единичных квадратов, которые являются частью полимино: $$$(i, l_i), (i, l_i + 1), \ldots, (i, r_i-1), (i, r_i)$$$.

Два полимино являются конгруэнтными тогда и только тогда, когда вы можете точно совместить их друг с другом в результате перемещений. Обратите внимание, что вам не разрешается поворачивать или отражать полимино. Определите, возможно ли разбить данное выпуклое полимино на два непересекающихся связных полимино, конгруэнтных друг другу. Следующие примеры иллюстрируют допустимое разбиение каждого из двух выпуклых полимино, показанных выше:

Полученные части полимино не обязательно должны быть выпуклыми. Каждый единичный квадрат должен принадлежать ровно одной из двух частей разбиения.

$$$^{\text{∗}}$$$Полимино является связным тогда и только тогда, когда для любых двух единичных квадратов $$$u \neq v$$$, которые являются частью полимино, существует последовательность различных квадратов $$$s_1, s_2, \ldots, s_k$$$, такая, что $$$s_1 = u$$$, $$$s_k = v$$$, все $$$s_i$$$ являются частью полимино, и $$$s_i, s_{i+1}$$$ имеют общую сторону для каждого $$$1 \le i \le k - 1$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — количество строк полимино.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1\le l_i\le r_i\le 10^9$$$) — диапазон столбцов, которые являются частью полимино в $$$i$$$-й строке.

Гарантируется что площадь полимино является чётной. Другими словами, $$$\sum_{i=1}^n r_i - l_i + 1\equiv 0\pmod{2}$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую либо «YES» или «NO» — может ли полимино быть разбито на части, как описано в задаче.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes», и «YES» будут приняты как положительный ответ.

Пример
Входные данные
7
2
1 2
2 3
4
4 4
2 4
1 4
1 2
3
1 2
1 2
2 3
2
1 3
3 3
2
1 3
2 2
3
1 2
1 3
1 3
4
8 9
6 8
6 8
5 6
Выходные данные
YES
YES
NO
NO
NO
NO
YES
Примечание

Первый и второй наборы входных данных являются полимино, показанными в условиях задачи, и могут быть разбиты, как показано на рисунке из условия.

Можно показать, что полимино в третьем наборе входных данных, показанное ниже, невозможно разбить. Ни одно из следующих разбиений не является корректным:

В разбиении слева полимино нельзя совместить только перемещениями, а в разбиении справа полимино не являются связными.

Можно показать, что полимино в четвертом наборе входных данных, показанное ниже, не поддается разбиению.

Обратите внимание, что хотя вы можете разбить его на два прямоугольника размера $$$1 \times 2$$$, эти прямоугольники нельзя совместить перемещениями.