文理学院程序设计在线练习


江湖门派

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 31   Accepted Submission(s): 5
Problem Description

江湖之上,有很多的门派,武当、少林、绍大ACM集团……还有一些只身行走江湖之人。现在江湖之上一共有N个人,每个人都有一个编号,从1到N。江湖之上,人际关系错综复杂,相互认识的人往往会形成若干个门派。我们假设如果A和B相互认识,B和C相互认识,那么A和C也相互认识,那么A,B,C三人归为一个门派。现在你的任务是统计这江湖之上一共有多少个门派(一个人也能单独成为一派)。

Input

题目一共有T组测试数据。(T<=1000)
对于每一组测试数据,首先输入两个数N,M,分别表示总人数、一共有M种关系。接下去N行,每行输入两个数a,b,表示a和b相互认识。
(0<N<1000,0<M<N*(N-1)/2,1<=a,b<=N)

Output

对于每一组测试数据答案占一行。输出格式”Case #t:x y”,x表示有多少个门派,y表示人数最多的那个门派的人数。

Sample Input
2
2 1
1 2
3 1
2 3
Sample Output
Case #1:1 2
Case #2:2 2
Author

Gu Yubin

Source

2018新人赛