CF1278D.Segment Tree

As the name of the task implies, you are asked to do some work with segments and trees.

Recall that a tree is a connected undirected graph such that there is exactly one simple path between every pair of its vertices.

You are given $n$ segments $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$, $l_i \lt r_i$ for every $i$. It is guaranteed that all segments' endpoints are integers, and all endpoints are unique — there is no pair of segments such that they start in the same point, end in the same point or one starts in the same point the other one ends.

Let's generate a graph with $n$ vertices from these segments. Vertices $v$ and $u$ are connected by an edge if and only if segments $[l_v, r_v]$ and $[l_u, r_u]$ intersect and neither of it lies fully inside the other one.

For example, pairs $([1, 3], [2, 4])$ and $([5, 10], [3, 7])$ will induce the edges but pairs $([1, 2], [3, 4])$ and $([5, 7], [3, 10])$ will not.

Determine if the resulting graph is a tree or not.

正如题目名称所暗示的，你需要对线段和树进行一些操作。

回忆一下，树是一种连通的无向图，且其任意两个顶点之间恰好存在一条简单路径。

你将得到 $n$ 条线段 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$，其中对每个 $i$ 都有 $l_i \lt 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])$ 则不会产生边。

请判断所得到的图是否为一棵树。

The first line contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of segments.

The $i$-th of the next $n$ lines contain the description of the $i$-th segment — two integers $l_i$ and $r_i$ ($1 \le l_i \lt r_i \le 2n$).

It is guaranteed that all segments borders are pairwise distinct.

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）—— 表示线段的数量。

接下来的 $n$ 行中，第 $i$ 行描述第 $i$ 条线段——包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \lt r_i \le 2n$）。

保证所有线段的端点两两互不相同。

Print "YES" if the resulting graph is a tree and "NO" otherwise.

如果所得图是一棵树，则输出“YES”，否则输出“NO”。

The graph corresponding to the first example:

The graph corresponding to the second example:

The graph corresponding to the third example:

第一个示例对应的图：

第二个示例对应的图：

第三个示例对应的图：