题目描述

译自 ROI 2023 Day2 T2. Конференция

秋明科学和教育协会组织了一次会议，计划在会议期间举办 $n$ 个活动，编号为 $1$ 到 $n$。其中，第 $i$ 个活动由两个整数 $l_{i}$ 和 $r_{i}$ 表示，分别是活动的开始时间和结束时间。

由于一些活动可能会重叠或甚至完全重合，一个人不一定能参加会议的所有活动。我们认为，如果 $r_{i}<l_{j}$ 或 $r_{j}<l_{i}$，那么活动 $i$ 和 $j$ 就不会相交。

我们称一个活动集合是相容的，如果这个集合中的任意两个不同的活动都不相交。设会议中相容活动集合的最大大小为 $m$。我们称会议的饱和度为 $\frac{n}{m}$。

由于资金缩减，会议的组织者决定会议的活动数量将减少一半。为了保持会议的饱和度不变，他们希望相容活动集合的最大大小也减少一半。幸运的是，在原来的会议计划中活动数量 $n$，和最大相容活动集合的大小 $m$ 都为偶数。

请帮助组织者从原来计划的 $n$ 个活动中选择 $\frac{n}{2}$ 个活动，使得这些活动的最大相容集合的大小为 $\frac{m}{2}$。

输入格式

输入包含多组数据。第一行包含一个整数 $t\ (1 \leq t \leq 5\cdot 10^4)$，表示测试数据的组数。

每组测试数据的第一行包含一个整数 $n\ (2 \leq n \leq 10^5)$，表示原计划中的活动数量，保证 $n$ 为偶数。

接下来的 $n$ 行给出活动的描述。在第 $i$ 行包含两个整数 $l_{i}, r_{i}\ (1 \leq l_{i}<r_{i} \leq 10^{9})$，表示第 $i$ 个活动的开始时间和结束时间。

保证原计划中相容活动集合的大小 $m$ 是偶数。

输出格式

对于每组测试数据，输出一行包含 $\frac{n}{2}$ 个不同的活动编号，表示需要举办的活动。如果存在多个合法的答案，你可以输出任意一个。对于举办的活动，相容活动集合的最大大小应该等于 $\frac{m}{2}$。

2
8
12 14
1 3
2 4
1 10
5 6
7 9
8 10
11 13
6
1 2
2 4
1 2
1 4
5 7
6 8

2 5 3 4
1 2 3

图片展示了活动的情况。开始时间为 $l_{i}$，结束时间为 $r_{i}$ 的活动用线段 $\left[l_{i}, r_{i}\right]$ 表示。

上图表示样例中第一个测试数据的原始活动集合。其中一个可能的最大相容活动集合用粗虚线标出。

上图表示样例中第一个测试数据的答案对应的活动集合。其中一个可能的最大相容活动集合用粗虚线标出。

上图表示样例中第二个测试数据的原始活动集合。其中一个可能的最大相容活动集合用粗虚线标出。

上图表示样例中第二个测试数据的答案对应的活动集合。其中一个可能的最大相容活动集合用粗虚线标出。

数据范围与提示

令 $t$ 组测试数据中的 $n$ 之和为 $N$。

如果 $l_{i} \leq l_{j}<r_{j} \leq r_{i}$，我们说活动 $i$ 覆盖活动 $j$。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。