← 返回题目列表

Codeforces · 1399/F

F. 另一个片段子集

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

在坐标轴 $$$OX$$$ 上给定 $$$n$$$ 段。第 $$$i$$$ 段的边界为 $$$[l_i; r_i]$$$。 $$$l_i \le x \le r_i$$$ 成立的所有点 $$$x$$$ 都属于第 $$$i$$$ 段。

您的任务是选择给定线段集的最大大小(线段数量)子集,使得该子集中的每一对线段要么不相交,要么其中一个线段位于另一个线段内部。

两个段 $$$[l_i; r_i]$$$ 和 $$$[l_j; r_j]$$$ 如果没有公共点,则它们不相交。例如,段 $$$[1; 2]$$$ 和 $$$[3; 4]$$$, $$$[1; 3]$$$ 和 $$$[5; 5]$$$ 不相交,而线段 $$$[1; 2]$$$ 和 $$$[2; 3]$$$, $$$[1; 2]$$$ 和 $$$[2; 2]$$$ 相交。

段$$$[l_i; r_i]$$$ 位于 $$$[l_j 段内; r_j]$$$ 如果 $$$l_j \le l_i$$$ 和 $$$r_i \le r_j$$$。例如,段 $$$[2; 2]$$$, $$$[2, 3]$$$, $$$[3; 4]$$$ 和 $$$[2; 4]$$$ 位于 $$$[2 段内; 4]$$$,而$$$[2; 5]$$$ 和 $$$[1; 4]$$$ 不是。

您必须回答 $$$t$$$ 独立测试用例。

输入

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

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3000$$$) — 段数。接下来的 $$$n$$$ 行描述段。第 $$$i$$$ 段由两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$) 给出,其中 $$$l_i$$$ 是第 $$$i$$$ 段的左边界,$$$r_i$$$ 是第 $$$i$$$ 段的右边界。第$$$i$$$段。

输入的附加约束:段列表中没有重复项。

保证$$$n$$$的总和不超过$$$3000$$$ ($$$\sum n \le 3000$$$)。

输出

对于每个测试用例,打印答案:给定线段集的子集的最大可能大小,使得该子集中的每一对线段要么不相交,要么其中一个位于另一个线段内部。

示例

输入 #1

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

输出 #1

3
4
2
7