#P0997. 通信协议
通信协议
题目描述
一支联合科考队共有 名队员。为了在不同设备和地区之间传递信息,科考队准备了 种通信协议,编号为 到 。
每名队员可能已经掌握若干种通信协议,也可能一种都不会。若两名队员掌握至少一种相同的协议,他们就可以直接交流;如果不能直接交流,也可以通过其他队员逐步转达信息。也就是说,只要所有队员在 “能够交流” 的关系中连成一个整体,任意两名队员就都可以完成通信。
现在科考队可以安排队员学习新的通信协议。每名队员学习一种协议的费用为 。队员可以学习任意多种协议。
请你计算,为了让任意两名队员都能够通过直接或间接的方式通信,科考队至少需要花费多少费用。
输入格式
第一行包含两个整数 和 ,表示队员人数和通信协议种类数。
接下来的 行,每行描述一名队员已经掌握的通信协议。第 行以整数 开头,表示第 名队员掌握的协议数量;接下来有 个整数 ,表示这些协议的编号。
保证每名队员的协议列表中没有重复编号。
输出格式
输出一个整数,表示使所有队员都能互相通信所需的最小费用。
样例
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
0
8 7
0
3 1 2 3
1 1
2 5 4
2 6 7
1 3
2 7 4
1 1
2
2 2
1 2
0
1
样例1解释
在样例 中,所有队员已经可以通过已有通信协议直接或间接地联系到彼此,因此不需要额外学习任何协议,答案为 。
数据范围
对于 的数据,,,。