← 返回题目列表

Codeforces · 31/C

C. 时间表

中文机器翻译题面 查看原题

新学期伊始,伯兰州立大学有新的日程安排。根据这个时间表,n个小组在31室上课。对于每个小组,课程的开始时间和课程的结束时间是已知的。事实证明,不可能举办所有课程,因为对于某些小组来说,他们的课程时间是交叉的。如果在某个时刻,一组完成了课程,而另一组开始了课程,那么他们的课程不会交叉。

院长想要取消一组的课程,以便其余组的两个课程时间段不交叉。你要找到一切方法来做到这一点。

输入

第一行包含整数 n (1 ≤ n ≤ 5000) — 在 31 号教室上课的组数。接下来的 n 行,每行包含两个整数 li ri (1 ≤ li < ri ≤ 106) — 第 i 组的上课时间和结束时间。最初可能没有两个课程相交(参见示例 1)。

输出

输出整数k——在一组中取消课程的方式数量,使得其余组的课程的两个时间段不相交。在第二行中输出 k 个数字——组的索引,其中可以取消课程。组按照输入中给出的顺序从 1 开始编号。按升序输出数字。

示例

输入 #1

3
3 10
20 30
1 3

输出 #1

3
1 2 3

输入 #2

4
3 10
20 30
1 3
1 39

输出 #2

1
4

输入 #3

3
1 5
2 6
3 7

输出 #3

0