# ROI 23 Conference

https://www.acmicpc.net/problem/28501

The Tyumen Association of Scientific and Educational Communities is organizing a conference, during which it was planned to hold $n$ events, numbered from $1$ to $n$. Each event $i$ is defined by two integers $l_i$ and $r_i$ — the start and end times of the event.

Since some events may overlap or even coincide entirely in time, not everyone can attend all conference events. We will consider that events $i$ and $j$ do not intersect if $r_i < l_j$ or $r_j < l_i$.

A set of events is called compatible if any two different events in this set do not intersect. Let the maximum size of a compatible set of events at the conference be $m$. We define the conference saturation as the ratio $n/m$.

Due to reduced funding, the conference organizers have decided to reduce the number of events at the conference by exactly half. However, they want to maintain the conference saturation unchanged, so the maximum size of a compatible set of events within the conference should also decrease by exactly half. Fortunately, it turned out that in the original conference plan, both the number of events $n$ and the maximum possible number of events in a compatible set $m$ are even numbers.

Help the organizers choose a set of $n/2$ initially planned events that need to be held, so that the size of the maximum compatible set of selected events is equal to $m/2$.

## Input

One test contains several sets of input data.

The first line contains a single integer $t$ — the number of sets of input data ($1 \le t \le 50,000$).

Each description of a set starts with a single integer $n$ — the number of events in the original plan ($2 \le n \le 100,000$, $n$ is even).

In the following $n$ lines of each set description, the description of events is given. The $i$-th line contains two integers $l_i$ and $r_i$ — the start and end times of the $i$-th event ($1 \le l_i < r_i \le 10^9$).

It is guaranteed that $m$, the size of the maximum compatible set of events for the original plan, is even.

## Output

For each set of input data, output in a new line $n/2$ distinct event numbers that need to be held. If there are multiple suitable answers, you can output any of them. For the held events, the size of the maximum compatible set of events should be equal to $m/2$.

## Subtasks

Denote the sum of $n$ over all sets of input data in one test as $N$.

We say that event $i$ covers event $j$ if $l_i \le l_j < r_j \le r_i$.

## Subtasks

| ID | Points | Constraints |
|----|--------|------------------------------------------|
| 1 | 5 | $N \leq 100\,000$, Any two events do not overlap |
| 2 | 20 | $N \leq 20$ |
| 3 | 7 | $N \leq 30$ |
| 4 | 15 | $N \leq 500$, In each pair of events, either one event covers the other or they do not intersect, and there exists an event that covers all others |
| 5 | 15 | $N \leq 100\,000$, In each pair of events, either one event covers the other or they do not intersect |
| 6 | 13 | $N \leq 500$ |
| 7 | 13 | $N \leq 5,000$ |
| 8 | 12 | $N \leq 100\,000$ |

## Sample

### Input

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

### Output

2 5 3 4
1 2 3


Fig. 1: The initial set of events in the first set of input data in the example. One of the possible maximum compatible sets is highlighted with thick dashed lines.


Fig. 2: The set of events corresponding to the answer for the first set of input data in the example. One of the possible maximum compatible sets is highlighted with thick dashed lines.


Fig. 3: The initial set of events in the second set of input data in the example. One of the possible maximum compatible sets is highlighted with thick dashed lines.


Fig. 4: The set of events corresponding to the answer for the second set of input data in the example. One of the possible maximum compatible sets is highlighted with thick dashed lines.