C. 双重视角

• 每个测试的时间限制：2 秒
• 内存限制：256 MB

对于一个由若干对 $(a_i, b_i)$ 构成的集合 $S = \{(a_1, b_1), (a_2, b_2), \dots, (a_m, b_m)\}$，其中对所有 $1 \le i \le m$ 有 $a_i < b_i$，我们定义 $f(S)$ 和 $g(S)$ 如下：

• 将每个 $(a_i, b_i)$ 视为数轴上的一个区间，$f(S)$ 表示这些区间的并集的长度。形式化地说，$f(S)$ 等于满足以下条件的整数 $x$ 的个数：存在某个 $i$（$1 \le i \le m$），使得 $[x, x+1] \subseteq [a_i, b_i]$。

• 将每个 $(a_i, b_i)$ 视为图中一条无向边，$g(S)$ 表示位于至少一个长度 $\ge 3$ 的简单环上的节点个数。形式化地说，$g(S)$ 等于满足以下条件的节点 $x_1$ 的个数：存在一条路径 $x_1 \to x_2 \to \dots \to x_k \to x_1$，其中 $k \ge 3$，且 $x_1, x_2, \dots, x_k$ 互不相同。

例如，对于 $S = \{(1,2), (2,4), (1,4), (4,5), (6,7)\}$，我们可以得到 $f(S) = 5$，$g(S) = 3$。

现在给你 $n$ 个不同的对。你需要从中选出一个子集 $S'$，使得 $f(S') - g(S')$ 的值最大。你需要输出所选对的下标。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^3$）。

接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i < b_i \le 2n$），表示一个对。

保证同一测试用例内的所有对都是不同的。

保证所有测试用例的 $n^2$ 之和不超过 $9 \times 10^6$。

输出格式

对于每个测试用例：

• 第一行输出一个整数 $k$（$0 \le k \le n$）—— 所选子集 $S'$ 的大小。
• 第二行输出 $k$ 个整数 $i_1, i_2, \dots, i_k$（$1 \le i_j \le n$）—— 所选对的下标。注意下标必须互不相同。

输入输出样例

样例输入

2
1
1 2
4
1 2
2 3
1 3
3 5

样例输出

1
1
3
1 2 4

样例解释

• 第一个测试用例：如果不选任何对（即 $S' = \varnothing$），则 $f(S') - g(S') = 0 - 0 = 0$。如果选第一个对，则 $f(S') - g(S') = 1 - 0 = 1$。因此最优解是选第一个对。