A83481.Learning Languages
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
“BerCorp”公司有 n 名员工。这些员工可以使用 m 种被批准的官方语言进行正式通信。语言用整数 1 到 m 编号。对于每位员工,我们知道他掌握的语言列表。这个列表可能为空,也就是说员工可能不懂任何官方语言。但员工们愿意学习任意数量的官方语言,只要公司为他们的课程付费。每名员工学习一门语言的费用为 1 伯币。
请你计算公司需要花费的最少总金额,使得任何一位员工都能够与任何其他员工进行通信(通信可以是间接的,即其他员工可以协助翻译)。
输入格式
第一行包含两个整数 n 和 m(2≤n,m≤100)——员工人数和官方语言数量。
接下来的 n 行,每行描述一名员工掌握的语言。第 i 行以整数 ki 开头(0≤ki≤m),表示第 i 位员工会的语言数。接下来是 ki 个整数 aij(1≤aij≤m),表示他会的语言的编号。保证每个列表中的语言编号各不相同。注意,有些员工可能不会任何语言。
同一行的数字用一个空格分隔。
输出格式
输出一个整数,表示使得任何员工都能与其他所有员工通信所需的最少费用。
输入输出样例
输入#1
5 5 1 2 2 2 3 2 3 4 2 4 5 1 5
输出#1
0
输入#2
8 7 0 3 1 2 3 1 1 2 5 4 2 6 7 1 3 2 7 4 1 1
输出#2
2
输入#3
2 2 1 2 0
输出#3
1
说明/提示
样例说明
在第二个样例中,第 1 号员工可以学习语言 2,第 8 号员工可以学习语言 4。
在第三个样例中,第 2 号员工必须学习语言 2。