P11109 [ROI 2023] 会议 (Day 2)

翻译自 [ROI 2023 D2T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day2.pdf)。 秘鲁科学和教育协会正在组织一次会议，计划进行 $n$ 个活动，编号从 $1$ 到 $n$。$l_i$ 和 $r_i$ 分别表示第 $i$ 个活动的开始和结束时间。由于某些活动可能冲突，一个人不一定能参加所有会议活动。如果 $r_i < l_j$ 或者 $r_j < l_i$，则认为活动 $i$ 和 $j$ 不冲突。 如果在同一个集合中任意两个不同的活动不冲突，则称该集合为相互兼容的。假设会议中最大相互兼容集合的大小为 $m$。则将会议的饱和度定义为 $\frac{n}{m}$。由于资金减少，会议组织者决定减少一半数量的会议活动。同时，他们希望会议的饱和度保持不变，因此在减少的会议活动中，最大相互兼容集合的大小也必须减少一半。 本题保证在原始会议计划中，会议活动的数量 $n$ 和最大兼容集合的大小 $m$ 恰好都是偶数。

请帮助组织者选择 $\frac{n}{2}$ 个计划中的会议活动，以使所选活动的最大兼容集合的大小为 $\frac{m}{2}$。

每个测试点包含多组数据。 第一行包含一个整数 $t$，即输入数据集的数量（$1 \le t \le 50000$）。 每组数据的第一行包含一个整数 $n$，即原始计划中的活动数量（$2 \le n \le 100000$，$n$ 是偶数）。 在接下来的 $n$ 行中，对于每个数据集的描述，给出了活动的描述。每行包含两个整数 $l_i$ 和 $r_i$，分别是第 $i$ 个活动的开始和结束时间（$1 \le l_i < r_i \le 10^9$）。 保证原始计划的最大兼容集合的大小 $m$ 是偶数，且 $\sum n\le100000$。

对于每组数据，在一行中输出 $\frac{n}{2}$ 个不同活动的编号，即保留下来的应该进行的活动编号。如果有多个合适的答案，可以输出任意一个。所选择的活动的最大相互兼容集合的大小应为 $\frac{m}{2}$。

样例解释：  上图是第一组输入数据中的初始活动集合。其中一种可能的最大相互兼容集合用粗虚线标出。  上图是第一组输入数据的答案的活动集合。其中一种可能的最大相互兼容集合用粗虚线标出。  第二组输入数据初始时的活动集合。  第二组输入数据答案中的活动集合。 设 $N=\sum n$。我们称活动 $i$ 完全覆盖活动 $j$，当且仅当 $l_i\le l_j