娜娜梦游仙境系列——多民族王国

TimeLimit:1000MS  MemoryLimit:64MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

娜娜好不容易才回忆起自己是娜娜而不是什么Alice,也回忆起了自己要继续探索这个世界的目标,便偷偷溜出皇宫。娜娜发现这个王国有很多个民族组成,每个民族都有自己的方言,更要命的是这些方面差别还很远,这就导致这个王国的人民交流十分困难。娜娜仔细观察并记录了好久,发现总共有m种不同的语言。

突然娜娜发现前面有一群天才在讨论问题,但是奈何语言问题,导致这群人交流非常吃力。不过幸亏的是,这群天才都有一个特殊的能力,只要消耗一个单位的能量即可完全领悟一门新的语言(妈妈再也不用担心我的四六级托福雅思GRE!)。于是娜娜久违的的好奇心又开始冒泡了,娜娜希望你告诉她,如果知道了每个人会的语言,是否能让这群天才两两直接或者间接的交流呢?所谓间接得交流是指经过若干个人的翻译使两个人得到相互表达的信息。如果不能,至少需要多少能量才能实现呢?

Input

多组数据,首先是一个正整数t(t<=20)

对于每组数据,首先是两个整数n,m(2<=n<=100,1<=m<=100),分别代表人数以及语言的种类数,语言的编号从1~m。

接下来是n行,每行对这个人进行描述

首先是一个整数k,表示这个人已经会k门语言,接下来是k个整数,分别是这个人掌握的语言编号。(0<=k<=m)

Output

对于每组数据,输出一个整数,表示使得这群人能够互相直接或者间接交流所需要的最少能量。

SampleInput
2
2 2
1 2
0
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
SampleOutput
1
0
提示:
样例1中其中第一个人会第二种语言,而第二个人不会任何语言,所以只需要第二个人也学会第二种语言即可交流,所以能量数为1
样例2中有5个人,而且这5个人已经可以相互直接或间接进行交流: 1-2-3-4-5,正好构成一条链。因此不需要继续学习新的语言,能量数为0。
Submit
题目统计信息详细
总AC数107
通过人数64
尝试人数67
总提交量313
AC率20.45%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: