← 返回题目列表

Codeforces · 1278/D

D. 线段树

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

正如任务名称所暗示的那样,您需要对线段和树进行一些处理。

回想一下,树是一个连通的无向图,其每一对顶点之间都存在一条简单路径。

对于每个 $$$i$$$,您将获得 $$$n$$$ 段 $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$, $$$l_i < r_i$$$。保证所有线段的端点都是整数,并且所有端点都是唯一的 - 不存在一对线段,它们从同一点开始,在同一点结束,或者一个从同一点开始另一个结束。

让我们用这些线段中的 $$$n$$$ 顶点生成一个图。顶点 $$$v$$$ 和 $$$u$$$ 通过边连接当且仅当线段 $$$[l_v, r_v]$$$ 和 $$$[l_u, r_u]$$$ 相交并且它们都不完全位于另一个内部。

例如,对 $$$([1, 3], [2, 4])$$$ 和 $$$([5, 10], [3, 7])$$$ 将产生边缘,但对 $$$([1, 2], [3, 4])$$$ 和 $$$([5, 7], [3, 10])$$$ 不会产生边缘。

确定生成的图是否是树。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 段数。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含第 $$$i$$$ 段的描述 — 两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le 2n$$$)。

保证所有段边界都是成对不同的。

输出

如果生成的图形是树,则打印“YES”,否则打印“NO”。

示例

输入 #1

6
9 12
2 11
1 3
6 10
5 7
4 8

输出 #1

YES

输入 #2

5
1 3
2 4
5 9
6 8
7 10

输出 #2

NO

输入 #3

5
5 8
3 6
2 9
7 10
1 4

输出 #3

NO

注意

第一个例子对应的图:

第二个例子对应的图:

第三个例子对应的图: