[R20F]构图判树 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

你有 $n$ 条线段，第 $i$ 条线段为闭区间 $[l_i, r_i]$。我们定义线段 $i$ 包含线段 $j$ 当且仅当满足：

• $l_i \leq l_j$ 且 $r_j \leq r_i$（端点可以重合）。

现在你需要根据所有满足包含关系的线段对，构建一个无向图：

• 每当线段 $i$ 包含线段 $j$，就在点 $i$ 和点 $j$ 之间连一条无向边。

请判断，这个图是否是一棵树。

格式

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

接下来每组测试数据格式如下：

第一行一个整数 $n$，表示线段的数量。

接下来 $n$ 行，每行两个整数 $l_i$ 和 $r_i$，表示第 $i$ 条线段的左右端点。保证不存在两个线段相同。

输出格式

输出共 $T$ 行，每行对应一组测试数据的判断结果。如果该组测试数据中，按照包含关系构建出的无向图构成一棵树，输出 Yes；否则输出 No。

样例

样例输入 #1

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

样例输出 #1

Yes
No

样例解释 #1

第一个样例中，线段 $1$ 包含 $2$ 和 $3$，线段 $2$ 与 $3$ 无直接包含关系，所以边为：$1-2$，$1-3$，形成一棵树。

第二个样例中，图中的边为 $1-2$，$1-3$，$1-4$，$2-3$，$2-4$，$3-4$。故该图不是一棵树。

数据规模

对于 $20\%$ 的数据，$1 \leq n \leq 100$。

对于 $100\%$ 的数据，$1 \leq T \leq 100$， $1 \leq n \leq 10^5$，$1 \leq l_i \leq r_i \leq 10^9$，$\sum n \leq 10^6$。

本题添加了赛后hack数据，由于OJ限制，本题满分为 101 分。（其中 1 分为赛后hack数据的得分）