Background

Translated from ROI 2023 D2T2。

The Peruvian Association of Science and Education is organizing a conference and plans to hold $n$ activities, numbered from $1$ to $n$. Let $l_i$ and $r_i$ be the start and end times of activity $i$, respectively. Since some activities may overlap, a person may not be able to attend all of them. Activities $i$ and $j$ are considered non-conflicting if $r_i < l_j$ or $r_j < l_i$.

A set of activities is called compatible if every two different activities in the set are non-conflicting. Suppose the maximum size of a compatible set is $m$. The saturation of the conference is defined as $\frac{n}{m}$. Due to budget cuts, the organizers decided to reduce the number of conference activities by half. At the same time, they want the saturation to remain unchanged, so in the reduced set of activities, the maximum size of a compatible set must also be reduced by half.

It is guaranteed that, in the original conference plan, both the number of activities $n$ and the maximum compatible set size $m$ are even.

Problem Description

Help the organizers choose $\frac{n}{2}$ activities from the plan so that the maximum size of a compatible set among the chosen activities is $\frac{m}{2}$.

Input Format

Each test contains multiple test cases.

The first line contains an integer $t$, the number of test cases ($1 \le t \le 50000$).

The first line of each test case contains an integer $n$, the number of activities in the original plan ($2 \le n \le 100000$, and $n$ is even).

In the next $n$ lines, the activities are described. Each line contains two integers $l_i$ and $r_i$, the start and end times of activity $i$ ($1 \le l_i < r_i \le 10^9$).

It is guaranteed that the maximum compatible set size $m$ in the original plan is even, and $\sum n\le100000$.

Output Format

For each test case, output $\frac{n}{2}$ distinct activity indices in one line, representing the activities that will be kept. If there are multiple valid answers, output any of them. The maximum size of a compatible set among the selected activities must be $\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

Hint

Sample explanation:

The figure above shows the initial set of activities in the first test case. One possible maximum compatible set is marked with a thick dashed line.

The figure above shows the set of activities in one valid answer for the first test case. One possible maximum compatible set is marked with a thick dashed line.

The initial set of activities in the second test case.

The set of activities in one valid answer for the second test case.

Let $N=\sum n$. We say that activity $i$ completely covers activity $j$ if and only if $l_i\le l_j<r_j\le r_i$.

Translated by ChatGPT 5