无所不在的宗教

Grade 100 Open Time Thursday, 18 June 2020, 11:10 AM
Discount 0.8 Time Discount Thursday, 18 June 2020, 11:10 AM
Allow late Yes Close Time Thursday, 18 June 2020, 11:10 AM
Input file religion.in Output file religion.out

【题目描述】无所不在的宗教(religion)POJ 2524

学院有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