2860. 战争之王

单点时限: 2.0 sec

内存限制: 256 MB

小王号称战争之王,他遇到敌手直到小周的出现。今天小王又遇到小周,一场大战在所难免,但是为了避免两败俱伤,他们决定玩自己开发的拳皇游戏来决定胜负。小王先开始选角色,小周只能从小王挑选剩下的角色中挑选。小王知道在双方选定了某些特定的角色后自己可以肯定打败小周,比如小王选择了角色 A,小周选择了角色 B,小王一定可以打败小周。

现在小王知道了所有这样的选择组合,请帮小王选择最少的角色数量以保证一定可以完全打败小周。

输入格式

多组测试数据(组数不大于 100),每组测试数据格式如下:

第一行有两个数字 n,m(1<=n,m<=100).

第二行有 n 个名字,以空格隔开,名字的长度不大于 20.

接下来有 m 行,每行以名字 A 开头,然后一个整数 mi(1<=mi<=n), 接下来 mi 个名字,以空格隔开,表示角色 A 可以打败这些角色。

输出格式

每组测试数据:

输出一行,表示小王最少需要选择的角色数 .

样例

Input
3 2
KYO MAI IORI
KYO 1 MAI
IORI 1 MAI
3 1
BENIMARU LEONA TERRY
BENIMARU 2 LEONA TERRY
3 1
BENIMARU LEONA TERRY
BENIMARU 1 LEONA
Output
2
1
2
Hint:
小王选择KYO 和IORI
小王 选择BENIMARU
小王 选择BENIMARU 和TERRY

2 人解决,13 人已尝试。

9 份提交通过,共有 38 份提交。

9.6 EMB 奖励。

创建: 8 年,12 月前.

修改: 2 年,4 月前.

最后提交: 3 年,10 月前.

来源: N/A

题目标签