Intervals

Time Limit: 1 Second
Memory Limit: 65536 KB
Special Judge

Chiaki has `n` intervals and the `i`-th of them is [`l`_{i}, `r`_{i}]. She wants to delete some intervals so that there does not exist three intervals `a`, `b` and `c` such that `a` intersects with `b`, `b` intersects with `c` and `c` intersects with `a`.

Chiaki is interested in the minimum number of intervals which need to be deleted.

Note that interval `a` intersects with interval `b` if there exists a real number `x` such that `l`_{a} ≤ `x` ≤ `r`_{a} and `l`_{b} ≤ `x` ≤ `r`_{b}.

#### Input

There are multiple test cases. The first line of input contains an integer `T`, indicating the number of test cases. For each test case:

The first line contains an integer `n` (1 ≤ `n` ≤ 50000) -- the number of intervals.

Each of the following `n` lines contains two integers `l`_{i} and `r`_{i} (1 ≤ `l`_{i} < `r`_{i} ≤ 10^{9}) denoting the `i`-th interval. Note that for every 1 ≤ `i` < `j` ≤ `n`, `l`_{i} ≠ `l`_{j} or `r`_{i} ≠ `r`_{j}.

It is guaranteed that the sum of all `n` does not exceed 500000.

#### Output

For each test case, output an integer `m` denoting the minimum number of deletions. Then in the next line, output `m` integers in increasing order denoting the index of the intervals to be deleted. If `m` equals to 0, you should output an empty line in the second line.

#### Sample Input

1
11
2 5
4 7
3 9
6 11
1 12
10 15
8 17
13 18
16 20
14 21
19 22

#### Sample Output

4
3 5 7 10

Author:

**LIN, Xi**
Source:

**The 17th Zhejiang University Programming Contest Sponsored by TuSimple**
Submit
Status