A83481.Learning Languages

普及-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

“BerCorp”公司有 nn 名员工。这些员工可以使用 mm 种被批准的官方语言进行正式通信。语言用整数 11mm 编号。对于每位员工,我们知道他掌握的语言列表。这个列表可能为空,也就是说员工可能不懂任何官方语言。但员工们愿意学习任意数量的官方语言,只要公司为他们的课程付费。每名员工学习一门语言的费用为 11 伯币。

请你计算公司需要花费的最少总金额,使得任何一位员工都能够与任何其他员工进行通信(通信可以是间接的,即其他员工可以协助翻译)。

输入格式

第一行包含两个整数 nnmm2n,m1002 \leq n,m \leq 100)——员工人数和官方语言数量。

接下来的 nn 行,每行描述一名员工掌握的语言。第 ii 行以整数 kik_i 开头(0kim0 \leq k_i \leq m),表示第 ii 位员工会的语言数。接下来是 kik_i 个整数 aija_{ij}1aijm1 \leq a_{ij} \leq 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
    

说明/提示

样例说明
在第二个样例中,第 11 号员工可以学习语言 22,第 88 号员工可以学习语言 44

在第三个样例中,第 22 号员工必须学习语言 22

首页