Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3953
Intervals

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

Chiaki has n intervals and the i-th of them is [li, ri]. 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 laxra and lbxrb.

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 li and ri (1 ≤ li < ri ≤ 109) denoting the i-th interval. Note that for every 1 ≤ i < jn, lilj or rirj.

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.

```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