练习专区

某运动会设立N个比赛项目，每个运动员可以参加1~3个项目。试问如何安排比赛日程，既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程最短。 例如：某一运动会有9个项目：A={0，1，2，3，4，5，6，7，8}，7名运动员报名的项目分别为：（1，4，8）、（1，7）、（8，3）、（1，0，5）、（3，4）、（5，6，2）和（6，4）。此问题就是将集合A划分成k个互不相交的子集A1，A2，…，Ak（k Input

先输入一个正整数T，表示有T种情况。 每一种情况的第一行有两个整数m、n，分别表示运动会的项目数m和运动员数n。接着n行，表示n个运动员参加的项目，每行第一个数是项目数，后面跟着相应的项目序号，序号从0开始。

Output

输出该运动会的各项比赛项目应分别安排在几个时间区内进行。

Sample Input

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

Sample Output

Case 1: 应安排在3个时间区进行。
Case 2: 应安排在1个时间区进行。

Hint

提交　　　　　返回

---