CF2055F.Cosmic Divide

With the artifact in hand, the fabric of reality gives way to its true master — Florida Man.

A polyomino is a connected$^{\text{∗}}$ figure constructed by joining one or more equal $1 \times 1$ unit squares edge to edge. A polyomino is convex if, for any two squares in the polyomino that share the same row or the same column, all squares between them are also part of the polyomino. Below are four polyominoes, only the first and second of which are convex.

You are given a convex polyomino with $n$ rows and an even area. For each row $i$ from $1$ to $n$, the unit squares from column $l_i$ to column $r_i$ are part of the polyomino. In other words, there are $r_i - l_i + 1$ unit squares that are part of the polyomino in the $i$-th row: $(i, l_i), (i, l_i + 1), \ldots, (i, r_i-1), (i, r_i)$.

Two polyominoes are congruent if and only if you can make them fit exactly on top of each other by translating the polyominoes. Note that you are not allowed to rotate or reflect the polyominoes. Determine whether it is possible to partition the given convex polyomino into two disjoint connected polyominoes that are congruent to each other. The following examples illustrate a valid partition of each of the two convex polyominoes shown above:

The partitioned polyominoes do not need to be convex, and each unit square should belong to exactly one of the two partitioned polyominoes.

$^{\text{∗}}$A polyomino is connected if and only if for every two unit squares $u \neq v$ that are part of the polyomino, there exists a sequence of distinct squares $s_1, s_2, \ldots, s_k$, such that $s_1 = u$, $s_k = v$, $s_i$ are all part of the polyomino, and $s_i, s_{i+1}$ share an edge for each $1 \le i \le k - 1$.

手握此物，现实的织锦便向其真正的主宰——佛罗里达男（Florida Man）臣服。

一个多联骨牌（polyomino）是由一个或多个全等的 $1 \times 1$ 单位正方形沿边拼接而成的连通$^{\text{∗}}$图形。若对多联骨牌中任意两个位于同一行或同一列的单位正方形，它们之间该行（或该列）上的所有单位正方形也均属于该多联骨牌，则称该多联骨牌为凸的（convex）。下图展示了四个多联骨牌，其中仅第一个和第二个是凸的。

现给定一个具有 $n$ 行的凸多联骨牌，且其总面积为偶数。对第 $i$ 行（$i = 1, 2, \dots, 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)$。

当且仅当可通过平移（translation）使两个多联骨牌完全重合时，称它们全等（congruent）。注意：不允许旋转或翻转多联骨牌。请判断：能否将给定的凸多联骨牌划分为两个互不相交且连通的多联骨牌，使得二者彼此全等？下图展示了上图所示两个凸多联骨牌各自的一种合法划分方式：

被划分出的多联骨牌无需为凸的；每个单位正方形必须且仅能属于划分所得的两个多联骨牌之一。

$^{\text{∗}}$一个多联骨牌是连通的，当且仅当对其中任意两个不同的单位正方形 $u \neq v$，均存在一串互异的正方形序列 $s_1, s_2, \ldots, s_k$，满足：$s_1 = u$，$s_k = v$，所有 $s_i$ 均属于该多联骨牌，且对每个 $1 \le i \le k - 1$，$s_i$ 与 $s_{i+1}$ 共享一条边。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of rows of the polyomino.

The $i$-th of the next $n$ lines contains two integers $l_i$ and $r_i$ ($1\le l_i\le r_i\le 10^9$) — the range of columns that are part of the polyomino in the $i$-th row.

It is guaranteed that the area of the polyomino is even. In other words, $\sum_{i=1}^n r_i - l_i + 1\equiv 0\pmod{2}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$）—— 表示多连方块（polyomino）的行数。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1\le l_i\le r_i\le 10^9$）—— 表示该多连方块在第 $i$ 行中所占据的列范围（即从第 $l_i$ 列到第 $r_i$ 列，含端点）。

保证该多连方块的面积为偶数，即 $\sum_{i=1}^n (r_i - l_i + 1)\equiv 0\pmod{2}$。

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

For each test case, print a single line containing either "YES" or "NO", representing whether or not the polyomino can be partitioned as described in the problem.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，输出一行，包含“YES”或“NO”，表示该多连方块是否能按题目描述的方式进行划分。

答案的大小写不限（即可以是大写或小写）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

The first and second test cases are the polyominoes depicted in the problem statement and can be partitioned as shown.

The polyomino in the third test case, shown below, can be shown to be impossible to partition. None of the following partitions are valid:

The partition on the left does not use polyominoes that are translations of each other, and the partition on the right does not use connected polyominoes.

The polyomino in the fourth test case, shown below, can be shown to be impossible to partition.

Note that while you can partition it into two $1 \times 2$ rectangles, these rectangles are not translations of each other.

第一和第二个测试用例是题目描述中所展示的多格骨牌，且可按图中所示方式进行划分。

第三个测试用例中的多格骨牌如下图所示，可以证明其无法被划分。以下任意一种划分方式均不合法：

左侧的划分未使用彼此平移得到的多格骨牌；右侧的划分未使用连通的多格骨牌。

第四个测试用例中的多格骨牌如下图所示，可以证明其无法被划分。

注意：尽管你可以将其划分为两个 $1 \times 2$ 的矩形，但这些矩形彼此之间并非平移关系。