ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6044: 附表

内存限制：256 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：4 通过：4
提交提交记录统计Web Board

题目描述

  在新学期开始时，伯兰州立大学有了新的时间表。根据这个时间表，n个小组在31号房间上课。对于每个组，课程的开始时间和课程的结束时间是已知的。事实证明，不可能举行所有课程，因为对于某些群体来说，他们的课程时间是交叉的。如果在某个时刻，一组完成课程，另一组开始课程，则他们的课程不会相交。
  院长希望取消一组的课程，以便其余小组的课程不会有两个时间段相交。你要找到所有的方法来做到这一点。



At the beginning of the new semester there is new schedule in the Berland State University. According to this schedule, n groups have lessons at the room 31. For each group the starting time of the lesson and the finishing time of the lesson are known. It has turned out that it is impossible to hold all lessons, because for some groups periods of their lessons intersect. If at some moment of time one groups finishes it's lesson, and the other group starts the lesson, their lessons don't intersect.
The dean wants to cancel the lesson in one group so that no two time periods of lessons of the remaining groups intersect. You are to find all ways to do that.
Input
The first line contains integer n (1≤n≤5000) − amount of groups, which have lessons in the room 31. Then n lines follow, each of them contains two integers li ri (1≤li<ri≤1000000) − starting and finishing times of lesson of the i-th group. It is possible that initially no two lessons intersect (see sample 1).
Output
Output integer k − amount of ways to cancel the lesson in exactly one group so that no two time periods of lessons of the remaining groups intersect. In the second line output k numbers − indexes of groups, where it is possible to cancel the lesson. Groups are numbered starting from 1 in the order that they were given in the input. Output the numbers in increasing order.
Examples
Input 
3
3 10
20 30
1 3
Output 
3
1 2 3
Input 
4
3 10
20 30
1 3
1 39
Output 
1
4
Input 
3
1 5
2 6
3 7
Output 
0

输入格式

第一行包含整数 n （1≤n≤5000）组的数量，这些小组在房间 31 中上课。然后是n行，每行包含两个整数li  ri（1≤li<ri≤1000000）第i组课程的开始和结束时间。最初可能没有两节课相交（见样本1）。

输出格式

输出整数 k （在一个组中取消课程的方法数量），以便其余组的课程没有两个时间段相交。在第二行输出k个数字组的索引，可以取消课程。组从 1 开始按输入中给出的顺序编号。按递增顺序输出数字。

输入样例 复制 

3
3 10
20 30
1 3

输出样例 复制 

3
1 2 3

分类标签