CF1841D.Pairs of Segments

Two segments $[l_1, r_1]$ and $[l_2, r_2]$ intersect if there exists at least one $x$ such that $l_1 \le x \le r_1$ and $l_2 \le x \le r_2$.

An array of segments $[[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]]$ is called beautiful if $k$ is even, and is possible to split the elements of this array into $\frac{k}{2}$ pairs in such a way that:

• every element of the array belongs to exactly one of the pairs;
• segments in each pair intersect with each other;
• segments in different pairs do not intersect.

For example, the array $[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$ is beautiful, since it is possible to form $3$ pairs as follows:

• the first element of the array (segment $[2, 4]$) and the third element of the array (segment $[2, 4]$);
• the second element of the array (segment $[9, 12]$) and the fifth element of the array (segment $[10, 13]$);
• the fourth element of the array (segment $[7, 7]$) and the sixth element of the array (segment $[6, 8]$).

As you can see, the segments in each pair intersect, and no segments from different pairs intersect.

You are given an array of $n$ segments $[[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]]$. You have to remove the minimum possible number of elements from this array so that the resulting array is beautiful.

两个线段 $[l_1, r_1]$ 和 $[l_2, r_2]$ 相交，当且仅当存在至少一个 $x$，使得 $l_1 \le x \le r_1$ 且 $l_2 \le x \le r_2$。

一个线段数组 $[[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]]$ 被称为优美的（beautiful），如果满足以下条件：

• $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]]$。你需要从中删除最少数量的元素，使得剩余数组是优美的。

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains one integer $n$ ($2 \le n \le 2000$) — the number of segments in the array. Then, $n$ lines follow, the $i$-th of them contains two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^9$) denoting the $i$-th segment.

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2000$.

第一行包含一个整数 $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$。

For each test case, print one integer — the minimum number of elements you have to remove so that the resulting array is beautiful.

对于每个测试用例，输出一个整数——即需要删除的最少元素个数，使得剩余数组是优美的。

In the first test case of the example, it is enough to delete the $5$-th element of the array of segments. Then you get the array $[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$, which is beautiful.

In the second test case of the example, you can delete the $1$-st, $3$-rd and $4$-th element of the array. Then you get the array $[[2, 8], [5, 6]]$, which is beautiful.

In the third test case of the example, you have to delete the whole array.

在示例的第一个测试用例中，只需删除数组中第 $5$ 个线段即可。此时得到的数组为 $[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$，该数组是优美的。

在示例的第二个测试用例中，可以删除数组中第 $1$、第 $3$ 和第 $4$ 个元素。此时得到的数组为 $[[2, 8], [5, 6]]$，该数组是优美的。

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