← 返回题目列表

Codeforces · 2055/F

F. 宇宙鸿沟

中文机器翻译题面 查看原题

有了这件神器,现实的结构让位给了它真正的主人——佛罗里达人。

多联骨牌是通过将一个或多个相等的 $$$1 \times 1$$$ 单位正方形边对边连接而成的连接 $$$^{\text{*}}$$$ 图形。如果对于共享同一行或同一列的任意两个方格,它们之间的所有方格也是该多格骨牌的一部分,则该多格骨牌是凸的。下面是四个多骨牌,只有第一个和第二个是凸面的。

给你一个凸多联骨牌,其中有 $$$n$$$ 行和偶数面积。对于从 $$$1$$$ 到 $$$n$$$ 的每一行 $$$i$$$,从列 $$$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)$$$。

当且仅当您可以通过平移多联骨牌使它们精确地叠放在一起时,两个多联骨牌才是全等的。请注意,您不能旋转或反射多骨牌。确定是否可以将给定的凸多格骨牌分割成两个互为全等的不相交的连接多格骨牌。以下示例说明了上面所示的两个凸多格骨牌中每一个的有效划分:

分割的多格骨牌不需要是凸的,并且每个单位正方形应该恰好属于两个分割的多格骨牌之一。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 多联骨牌的行数。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$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”将被识别为肯定响应。

示例

输入 #1

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

输出 #1

YES
YES
NO
NO
NO
NO
YES

注意

第一个和第二个测试用例是问题陈述中描述的多骨牌,可以如图所示进行分区。

第三个测试用例中的多联骨牌(如下所示)可以证明是不可能分割的。以下分区均无效:

左侧的分区不使用相互平移的多联骨牌,右侧的分区不使用连接的多联骨牌。

第四个测试用例中的多联骨牌(如下所示)可以证明是不可能划分的。

请注意,虽然您可以将其划分为两个 $$$1 \times 2$$$ 矩形,但这些矩形不是彼此的平移。