408002 - 爱好

学院有n(0<n≤50 000)个学生,已知有m(0≤m≤n(n-1)/2)对爱好相同的学生,请估算这n个学生中最少有多少种爱好。

输入

输入数据有多组,每一组以两个数字n,m开始,代表有n个学生,m对爱好相同的学生,随后的m行中,每行包含两个数字i和j,表示学生i和学生j的爱好相同。最后一行两个0代表输入结束。

输出

输出整数ans表示最少有多少种爱好,注意ans前面加上Case和组数和“:”。

样例

输入

10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0

输出

Case 1: 1
Case 2: 7
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题