← 返回题目列表

Codeforces · 1462/F

F. 段的宝藏

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

Polycarp 在街上发现了 $$$n$$$ 路段。索引为 $$$i$$$ 的段由两个整数 $$$l_i$$$ 和 $$$r_i$$$ 描述——分别是段的开头和结尾的坐标。坡旅甲意识到他不需要所有片段,因此他想删除其中一些片段。

Polycarp 认为,一组 $$$k$$$ 线段是好的,如果该组中有一个线段 $$$[l_i, r_i]$$$ ($$$1 \leq i \leq k$$$),这样它与该组中的每个线段相交(交集必须是一个点或线段)。例如,一组 $$$3$$$ 线段 $$$[[1, 4], [2, 3], [3, 6]]$$$ 就很好,因为线段 $$$[2, 3]$$$ 与该组中的每个线段相交。 $$$4$$$ 段集 $$$[[1, 2], [2, 3], [3, 5], [4, 5]]$$$ 不好。

Polycarp 想知道,为了使剩余的片段形成一个好的集合,他必须删除的最少片段数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 段数。接下来是描述段的 $$$n$$$ 行。

每个段由两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq 10^9$$$) 描述 - 分别是段的开头和结尾的坐标。

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

输出

对于每个测试用例,输出一个整数 - 需要删除的最小段数,以使剩余段集变得良好。

示例

输入 #1

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

输出 #1

0
1
2
0