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的关系,可以使得所有关系不存在矛盾。

Input

第一行T <= 10
接下来每个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