10118: 比较
Memory Limit:512 MB
Time Limit:4.000 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:0
Description
zhaoweijie12有n个数字,他不知道具体这n个数字是多少,但是他知道m组这些之间的大小关系(第ai个数小于第bi个数)。这些关系是否存在矛盾?
(如a < b, b < c, c < a,则矛盾)
输出一个最大的k,使得删除编号大于k的所有关系,只保留编号小于等于k的关系,可以使得所有关系不存在矛盾。
(如a < b, b < c, c < a,则矛盾)
输出一个最大的k,使得删除编号大于k的所有关系,只保留编号小于等于k的关系,可以使得所有关系不存在矛盾。
Input
第一行T <= 10
接下来每个case:第一行2个整数n m,(2 <= n <= 10000, 1 <= m <= 100000),接下来m行每行2个整数,a,b(1 <= a,b <= n),表示编号为a的数字小于到编号为b的数字。
接下来每个case:第一行2个整数n m,(2 <= n <= 10000, 1 <= m <= 100000),接下来m行每行2个整数,a,b(1 <= a,b <= n),表示编号为a的数字小于到编号为b的数字。
Output
每个case输出"Case x: y",x为从1开始的编号,y为对应输入中询问的答案。
Sample Input Copy
2
3 3
1 2
1 3
2 3
3 3
1 2
2 1
2 3
Sample Output Copy
Case 1: 3
Case 2: 1
HINT
Author: zhaoweijie12