题目描述

秋明科学与教育协会正在组织一场会议，计划举办 $n$ 场活动，编号从 $1$ 到 $n$。第 $i$ 场活动由两个整数 $l_i$ 和 $r_i$ 定义，分别表示活动的开始时间和结束时间。

由于某些活动可能会在时间上重叠甚至完全重合，一个人并不总能参加会议的所有活动。我们认为，如果 $r_i < l_j$ 或 $r_j < l_i$，则活动 $i$ 和 $j$ 不相交。

如果一个活动集合中任意两个不同的活动都不相交，我们称该集合为相容集合。设会议中相容活动集合的最大大小为 $m$。我们将会议的饱和度定义为 $n/m$。

由于经费缩减，会议组织者决定将会议的活动数量减少一半。同时，他们希望保持会议的饱和度不变，因此相容活动集合的最大大小也必须减少一半。幸运的是，在原始会议计划中，活动总数 $n$ 和最大相容活动集合的大小 $m$ 均为偶数。

请帮助组织者从原计划的 $n$ 场活动中选择 $n/2$ 场活动进行举办，使得所选活动中最大相容活动集合的大小恰好为 $m/2$。

输入格式

一个测试点包含多个输入数据。 第一行包含一个整数 $t$ —— 输入数据的组数 ($1 \le t \le 50\,000$)。 每个输入数据的第一行包含一个整数 $n$ —— 原始计划中的活动数量 ($2 \le n \le 100\,000$，$n$ 为偶数)。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$ —— 第 $i$ 场活动的开始和结束时间 ($1 \le l_i < r_i \le 10^9$)。 保证原始计划中最大相容活动集合的大小 $m$ 为偶数。

输出格式

对于每组输入数据，在单独的一行中输出 $n/2$ 个不同的活动编号，即需要举办的活动。如果存在多个合适的答案，你可以输出其中任意一个。对于所选的活动，其最大相容活动集合的大小必须等于 $m/2$。

子任务

设 $N$ 为单个测试点中所有输入数据的 $n$ 之和。 我们称活动 $i$ 覆盖活动 $j$，如果 $l_i \le l_j < r_j \le r_i$。

说明

图示可视化了活动。开始时间为 $l_i$、结束时间为 $r_i$ 的活动表示为区间 $[l_i, r_i]$。

图 1：示例中第一组输入数据的原始活动集合。其中一个最大相容集合用粗虚线标出。

图 2：对应示例中第一组输入数据答案的活动集合。其中一个最大相容集合用粗虚线标出。

图 3：示例中第二组输入数据的原始活动集合。其中一个最大相容集合用粗虚线标出。

图 4：对应示例中第二组输入数据答案的活动集合。其中一个最大相容集合用粗虚线标出。

样例

输入格式 1

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

输出格式 1

2 5 3 4
1 2 3