这是问题的简单版本。在此版本中,$$$n$$$ 的限制和时间限制较低。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
如果一组(闭合)段可以划分为一些子集,那么它就是复杂的
- 所有子集具有相同的大小;和
- 一对线段相交当且仅当两个线段位于同一子集中。
您将获得 $$$n$$$ 段 $$$[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$$$。找出这些段的复杂子集的最大大小。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^4$$$) — 段数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i \le 2n$$$) - 段的左端点。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$ ($$$l_i \leq r_i \le 2n$$$) - 线段的右端点。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^4$$$。
输出
对于每个测试用例,输出一个整数:给定段的复杂子集的最大大小。
示例
输入 #1
3 3 1 2 3 5 4 6 5 1 2 3 6 8 5 4 7 9 10 5 3 1 4 1 5 7 2 6 5 10
输出 #1
3 4 4
注意
在第一个测试用例中,所有线段对相交,因此最好形成包含所有三个线段的单个组。
在第二个测试用例中,所有五个段都没有有效的分区。具有四个段的有效分区如下:$$$\{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\}$$$。
在第三个测试用例中,最好创建一个包含除第二个之外的所有段的单个组。