OpenJudge

11:机智的导演

总时间限制:
10000ms
内存限制:
10000kB
描述

你是某歌手节目的总导演,你的任务很简单,安排每一期节目的内容。

现在有N个歌手,M种歌曲流派(Rock,Pop之类),每个歌手都有自己擅长的流派领域,这些资料都已整理好。你的工作是,安排尽可能多场的演唱比赛。每一场比赛所有歌手都必须上场,为了提高收视率,每个人演唱的歌曲类型不能相同,即便一些歌手要被迫选择一些他们不擅长的。同时,为了展现全面性,在不同的演唱比赛上,每个歌手都会安排不同的歌曲流派。

那么问题来了,对于任何一个歌曲流派的歌迷,如果超过K个不擅长的歌手演唱了这种歌曲,他们就会表示很不满,比如,发一些宣泄不满的帖子微博,为了表示观点挑起事端等等。你当然不希望这些事情影响你的节目,在这个前提下,你可以任意安排尽可能多的比赛场次。

输入
输入第一行为T,表示有T组测试数据。
每组数据以四个数字N,M,L, K开始。L表示有L组擅长关系,接下来的L行,每一行有两个数字Ai,Bi,表示歌手Ai擅长Bi类型的歌曲。

[Technical Specification]

1. 1 <= T <= 100
2. 1 <= N <= M <= 74, 0 <= K <= N
3. 0 <= L <= N*M
4. 1 <= Ai <= N, 1 <= Bi <= M, 相同关系不会重复出现
输出
对每组数据,先输出为第几组数据,然后输出最多比赛场次。
样例输入
3
1 1 1 0
1 1
1 3 0 1
3 3 5 1
1 1
1 2
2 2
2 3
3 1
样例输出
Case 1: 1
Case 2: 3
Case 3: 2
提示
对第三组样例,可以如此安排:
第一场三位歌手分别演唱(2,3,1)类型的歌曲,第二场分别演唱(1,2,3)。
这样只有类型3被不擅长的歌手演唱过1次,挑剔的歌迷观众还可以接受。
全局题号
14732
提交次数
2
尝试人数
1
通过人数
1