问题 4680 --学语言

4680: 学语言★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 84  解决: 43
[提交][状态][命题人:]

题目描述

锐拓编程公司有n名员工。这些员工可以使用m种被批准的官方语言进行交流。把这些语言用1m的整数进行编号。对于每个员工,我们有一份他所掌握的语言的列表。这个列表可能是空的,因为某个雇员可能一个官方语言都不会。但只要公司支付他们的课程费用,员工愿意学习任何数量的官方语言,每名员工学习一门语言的费用为1元。 

找出公司需要花费的最低金额,以便任意一个员工可以与其他员工交流(他们之间的交流可以是间接的,即其他员工可以帮助翻译)。

输入

第一行包含两个整数nm(2n, m100) -员工数量和语言数量。

 接下来n行-每个员工的语言列表。第i行的开头是整数ki(0 ≤ ki ≤ m) 即第i位员工掌握的语言数量。接下来,第i行包含ki个整数-aij (1 ≤ aij ≤ m) 即第i位员工掌握的语言编号。需要保证一个列表中每个编号都是不同的。请注意,员工可能不懂任何官方语言。

 行中的数字由单个空格分隔。

输出

输出一个整数-支付的最低金额,使最终每个员工都可以跟其他员工交流(员工之间可以帮助翻译)。

样例输入
Copy
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
样例输出
Copy
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

来源

[提交][状态]