2.4 Summer Camp

Score: 50pts

Time Limit: 2.00 sec

Our college is conducting workshops during the summer vacations. All students are divided into teams to attend the workshop. The workshops are going to be conducted in the seminar hall on the 11th floor. For each team of students their start and end time of the workshops are specified. As only one hall is provided no two or more workshops can intersect with each other.

The student council has been asked by the principal to cancel exactly one workshop so that the timing of remaining workshops doesn’t collide with each other.

Print the number of workshops that can be cancelled exactly once to create a non-intersecting schedule, along with their one-based indexes on the next line, for a given test case.

The student council has been asked by the principal to cancel exactly one workshop so that the timing of remaining workshops doesn’t collide with each other.

Print the number of workshops that can be cancelled exactly once to create a non-intersecting schedule, along with their one-based indexes on the next line, for a given test case.

Constraints

1 <= t <= 10

1 <= n <= 5000

1 <= s[i] < e[i] <= 10^6

1 <= n <= 5000

1 <= s[i] < e[i] <= 10^6

Input Format

The first line contains the number of test cases t

For each test case:

The first line contains the number of teams n

The following n lines would contain workshop i’s start time s[i] and end time e[i]

For each test case:

The first line contains the number of teams n

The following n lines would contain workshop i’s start time s[i] and end time e[i]

Output Format

For each test case-

Print the possible no of ways to cancel the workshop such that workshop timings doesn't intersect.

In the next line, if any, print the one-based index of the workshop that needs to be cancelled

Print the possible no of ways to cancel the workshop such that workshop timings doesn't intersect.

In the next line, if any, print the one-based index of the workshop that needs to be cancelled

Example 1

Input:

3

3

3 10

20 30

1 3

4

3 10

20 30

1 3

1 39

3

1 5

2 6

3 7

Output:

3

1 2 3

1

4

0

Explanation:

In the first case, we have 3 workshops where none of the timings collide with each other, and we need to cancel exactly one workshop, hence we have 3 ways of keeping the workshop keeping the given conditions in mind.

In the second case, we have 4 workshops, where the timings of the last workshop collide with all the other workshops, whereas the timings of other workshops don’t collide with each other, therefore that workshop gets cancelled each time and is the only one that gets cancelled, hence the output.

In the third case, we have 3 workshops where all their timings collide with each other, therefore we have no way to actually have all the other workshops together, hence the output 0.

3

3

3 10

20 30

1 3

4

3 10

20 30

1 3

1 39

3

1 5

2 6

3 7

Output:

3

1 2 3

1

4

0

Explanation:

In the first case, we have 3 workshops where none of the timings collide with each other, and we need to cancel exactly one workshop, hence we have 3 ways of keeping the workshop keeping the given conditions in mind.

In the second case, we have 4 workshops, where the timings of the last workshop collide with all the other workshops, whereas the timings of other workshops don’t collide with each other, therefore that workshop gets cancelled each time and is the only one that gets cancelled, hence the output.

In the third case, we have 3 workshops where all their timings collide with each other, therefore we have no way to actually have all the other workshops together, hence the output 0.