P1545Pugna看球赛 | |
|
问题描述
Pugna最近在看一个足球联赛。只是现在一场比赛都没开始,Pugna想知道最终哪些球队可以夺冠。
假设联赛采用淘汰赛的规则,就是一共n个球队以任意的顺序比赛,每场比赛都一定会角出胜负,负者直接淘汰。也就是说比赛n-1场之后就一定会出现冠军。
现在Pugna给每个球队都标记了一个“战斗力”的范围,一场比赛中双方的战斗力都不会超出这个范围(可以等),并且战斗力强的队伍获胜。如果双方战斗力相同,则两个球队都可能获胜。注意每个球队的战斗力可能在每场比赛中都不一样。
你的任务就是对于给定的n和所有的战斗力范围[Ai,Bi],求出所有可能夺冠的球队。
输入格式
第一行,一个整数n;
接下来n行,每行两个整数Ai,Bi表示编号为i的球队战斗力范围;
输出格式
以升序输出所有可能夺冠的球队编号。一行一个。
样例输入
样例输入1:
3
1 1
2 3
3 4
样例输入2:
5
1 5
2 5
3 6
4 5
999 9999
样例输出
样例输出1:
2
3
样例输出2:
5
提示
n<=10,0000
-20,0000,0000<Ai<=Bi<20,0000,0000