Problem2995--黑客的攻击[Hacker's Crackdown,UVa11825]

2995: 黑客的攻击[Hacker's Crackdown,UVa11825]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

Hackers' Crackdown在分布式系统上运行着许许多多的系统服务,是很多黑客的主要目标。
该系统有N个计算机节点,每个计算机节点上都运行着N项服务,每个节点上运行的所有服务都是相同的。
黑客终止一项服务,就是在每个计算机节点上运行这项服务的“exploit”。
一天,一个非常聪明的黑客,收集到了所有的这N项服务的“exploit”,并开始对系统发起了攻击。
服务的“exploit”都有一个特征:一项服务的“exploit”在一台计算机上运行后,这台计算机以及所有相邻的计算机都会被感染运行这个“exploit”
给定一个计算机网络拓扑描述,找到黑客能够终止的最大服务数(即所有的计算机节点上都终止了这项服务)。

Input

输入包含多组测试数据。
对于每组测试数据:
第一行,是一个整数N,表示网络中的计算机节点数,计算机节点的编号是0到N-1(1≤N≤16)
接下来N行,每行描述一个节点的状态,第i行描述结点i。每一行,第一个数是一个整数m,表示结点i的相邻节点的数量,接下来m个整数,表示m个相邻节点的编号(数据范围是0到N-1)

Output

对于每组测试数据,输出一行,输出格式为‘Case X: Y’,X表示测试数据的编号,Y表示能够终止的最大的服务数。

Sample Input Copy

3
2 1 2
2 0 2
2 0 1
4
1 1
1 0
1 3
1 2
0

Sample Output Copy

Case 1: 3
Case 2: 2

Source/Category