度度熊最近开始迷上了一款新游戏AotD，但无奈水平太菜，被虐了很多次之后，它决定来做点什么平衡一下这款游戏。

度度熊认为自己被虐的主要原因是游戏中存在一些克制关系：比如当他玩Sniper时，就常常被Pudge虐的找不着北。所以他决定Hack这个游戏，消除一些克制关系。任意一个英雄克制与被克制的英雄个数差值越小，这个游戏就越平衡，作为“平衡大师”，度度熊的目标也是让所有英雄的这个差值的绝对值的最大值最小。

当然，完全没有克制关系，这个游戏也就失去乐趣了，所以这种关系的个数应该不低于一个值，称之为游戏乐趣值。

注意，这个克制关系是由度度熊的游戏水平决定的：比如他玩Pudge时同样会被Sniper虐，所以它也认为Sniper克制Pudge。

第一行一个整数 T，表示 T 组数据。

每组数据第一行包含三个数：英雄个数 N，克制关系个数 M，游戏乐趣值 K。（1 \le N \le 50，0 \le K \le M \le N \times (N-1)）

然后接下来的 M 行，每行包含两个英雄名称 A 和 B，表示 A 克制 B，A 和 B 不会相同。不同名称的个数不会超过 N。名称长度不超过 20，且只包含字母。

度度熊很机智，在这个克制关系表中，同一个克制关系不会出现多次。

对于每组数据，先输出一行：

Case #i:

然后输出最小的最大差值。