Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3953

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.


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.


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

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

Sample Output

3 5 7 10

Author: LIN, Xi
Source: The 17th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status