社团的统计

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

在我们的大学里有许许多多的社团,很难掌握所有人参加了什么社团,现在xiaoyoulei在团委打杂,需要统计有多少个社团在我们学校存在。他知道学校有n(0 < n <= 50000)个学生,他去问每一个学生参加什么社团是不可能的。而且,许多同学也不想告诉他,一种方法解决这些问题,要求m(0 <= m <= n(n-1)/2)对同学,并询问他们是否在同一个社团(例如,他们可能互相知道,如果他们都出席同一社团会议)。从这些数据,你可能不知道每个人是否参加,但你可以得到的,究竟可能最多有多少社团同学们参加了。现在假设每个学生最多一个参加一个社团。xiaoyoulei很懒,希望你能帮他搞定。

Input

输入包含多组测试数据,每一组数据开始一行是俩个整数n和m。接下来的m行每行包括2个整数i和j,表示i和j参加了同一个社团,同学们从1到n被标号,输入以n=m=0结束。

Output

对于每个测试用例,输出在一行,形式"Case x: max";x表示第几组测试数据(从1开始),max是社团的最多可能数量。

Sample Input

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

Sample Output

Case 1: 1
Case 2: 7

Hint

Case 2: 7 1; 6; 7; 9; 10; 可能每个人在不同社团(可能5个不同社团) 2,3; 2,3在同一个社团 4,5,8; 4,5,8在同一个社团 所以最多可能存在有7个社团

Source

dreaming3000

提交代码