题意回顾

给定 $n$ 个配对 $(a_i, b_i)$，满足 $1 \le a_i < b_i \le 2n$。定义：

• $f(S)$：将 $S$ 中的配对视为数轴上的线段，线段并集包含的整数 $x$ 的个数，即满足 $\exists i$ 使 $[x, x+1] \subseteq [a_i, b_i]$ 的 $x$ 的数量，等价于所有线段的并的长度。
• $g(S)$：将 $S$ 中的配对视为无向边，图中至少处在一个长度 $\ge 3$ 的简单环上的节点个数。

要求选出一个子集 $S'$，最大化 $f(S') - g(S')$，输出所选配对的原始编号。

核心观察

性质 1：最优解中 $g(S') = 0$。

证明：假设最优解 $S'$ 中存在环，那么环上至少有一条边 $e$，将其删去后 $f(S')$ 不变。
这是因为环上至少有三条边，必然存在一个节点 $v$ 使得与它相邻的两条边对应的线段中，一条完全包含另一条，于是被包含的那条线段对并集没有贡献，删除它不改变 $f$。
而删边后 $g$ 可能减小或不变，$f-g$ 必不降。重复此操作可将所有环消去，且 $f$ 不减少。故存在一个最优解满足 $g=0$。

性质 2：当 $g(S)=0$ 时，图是一个森林。最大化 $f(S)$ 等价于在保证无环的前提下，使线段并尽可能大。

简化问题

既然最优解可以做到 $g=0$，我们只需要找出一个无环的边集，同时使线段并最大。
注意到：如果一条线段被另一条线段完全包含（即 $\exists j$ 使 $a_j \le a_i$ 且 $b_i \le b_j$），那么线段 $i$ 对并集没有任何额外贡献，移除它不会减小 $f$，同时还能帮助破坏环。因此我们可以安全地删除所有被其他线段包含的线段。

引理：
将所有被包含的线段删除后，剩余的线段构成的图一定没有长度 $\ge 3$ 的环。

证明：
设剩余线段中没有包含关系。若存在一个简单环 $x_1 - x_2 - \cdots - x_k - x_1$ ($k \ge 3$)，由于所有线段端点值互异且 $a_i<b_i$，我们可以在环上找到一个局部最大值 $x_p$，即 $x_{p-1} < x_p > x_{p+1}$（下标模 $k$）。
此时边 $(x_{p-1}, x_p)$ 和 $(x_p, x_{p+1})$ 对应的线段必然一个包含另一个，例如 $[x_{p-1}, x_p]$ 可能包含在 $[x_p, x_{p+1}]$ 中，这与“无包含关系”矛盾。故剩余线段构成无环图。

于是，删除所有被包含线段后的集合就是一个符合要求的最优解：

• $g=0$（因为无环）；
• $f$ 等于这些线段的并，也就是原所有 $n$ 条线段的总并，因为被删的线段都完全被其它线段覆盖，不会扩展并的范围。
  显然，任何子集都不可能让 $f$ 超过全部线段的并，所以该解使 $f$ 达到最大值。

算法步骤

对于每组测试用例：

1. 读入 $n$，记录每条线段的端点 $a_i, b_i$ 以及原始索引 $i$。
2. 使用双重循环检查每条线段 $i$ 是否被另一条线段 $j$ 严格包含（即 $a_j \le a_i$ 且 $b_i \le b_j$，且 $(a_j,b_j) \ne (a_i,b_i)$）。
   注意：根据题意所有配对互异，无需处理完全相等的情形。
3. 如果线段 $i$ 没有被任何其它线段包含，则将其索引加入答案集合。
4. 输出答案集合的大小 $k$，以及对应的 $k$ 个索引（顺序任意）。

正确性证明

• 最优性：由性质 1，存在最优解 $g=0$。此时 $f$ 不可能超过全部 $n$ 条线段的并的长度。而我们构造的集合（所有极大线段）恰好覆盖了整个原始并，且 $g=0$，故达到上界。
• $g=0$ 的保证：根据引理，极大线段集合构成的图无环，因此 $g=0$。

复杂度分析

检查包含关系需要 $O(n^2)$ 的时间。
题目保证所有测试用例的 $\sum n^2 \le 9 \times 10^6$，最坏情况下可接受。
空间复杂度 $O(n)$ 用于存储线段和标记。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i] >> b[i];
        }

        vector<bool> keep(n, true);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j || !keep[i]) continue;
                if (a[j] <= a[i] && b[i] <= b[j]) {
                    keep[i] = false; // i 被 j 包含
                }
            }
        }

        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (keep[i]) ans.push_back(i + 1);
        }

        cout << ans.size() << '\n';
        for (int x : ans) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

其他解法

也可以用并查集（DSU）动态维护生成森林，逐步加入线段，若加入后成环则跳过。但直接去包含的 $O(n^2)$ 方法更简洁，且完全满足题目数据范围。