← 返回题目列表

Codeforces · 1841/D

D. 段对

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

如果存在至少一个满足 $$$l_1 \le x \le r_1$$$ 和 $$$l_2 \le x \le r_2$$$ 的 $$$x$$$,则两条线段 $$$[l_1, r_1]$$$ 和 $$$[l_2, r_2]$$$ 相交。

如果 $$$k$$$ 是偶数,则段数组 $$$[[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]]$$$ 被称为美丽的,并且可以通过以下方式将该数组的元素拆分为 $$$\frac{k}{2}$$$ 对:

- 数组的每个元素都属于其中一对;
- 每对中的线段彼此相交;
- 不同对中的线段不相交。

例如,数组 $$$[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$$$ 很漂亮,因为可以按如下方式形成 $$$3$$$ 对:

- 数组的第一个元素(段 $$$[2, 4]$$$)和数组的第三个元素(段 $$$[2, 4]$$$);
- 数组的第二个元素(段 $$$[9, 12]$$$)和数组的第五个元素(段 $$$[10, 13]$$$);
- 数组的第四个元素(段 $$$[7, 7]$$$)和数组的第六个元素(段 $$$[6, 8]$$$)。

正如您所看到的,每对中的线段相交,并且不同对中的线段没有相交。

给你一个 $$$n$$$ 段 $$$[[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]]$$$ 的数组。您必须从该数组中删除尽可能少的元素,以便生成的数组很漂亮。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2000$$$) — 数组中的段数。然后是 $$$n$$$ 行,其中第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) 表示第 $$$i$$$ 段。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,打印一个整数 - 必须删除的最小元素数,以便生成的数组美观。

示例

输入 #1

3
7
2 4
9 12
2 4
7 7
4 8
10 13
6 8
5
2 2
2 8
0 10
1 2
5 6
4
1 1
2 2
3 3
4 4

输出 #1

1
3
4

注意

在示例的第一个测试用例中,删除段数组的第 $$$5$$$ 元素就足够了。然后你就得到了数组 $$$[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$$$,这很漂亮。

在示例的第二个测试用例中,您可以删除数组的第 $$$1$$$-st、$$$3$$$-rd 和 $$$4$$$-th 元素。然后你得到数组$$$[[2, 8], [5, 6]]$$$,这很漂亮。

在示例的第三个测试用例中,您必须删除整个数组。