题目描述

在 Google，我们喜欢互相教授新技能！公司有 $N$ 名员工，编号为 $1$ 到 $N$。一共有 $S$ 种不同的技能，编号为 $1$ 到 $S$。每名员工最多掌握 $5$ 种不同的技能。

如果第 $i$ 名员工掌握了一项第 $j$ 名员工未掌握的技能，那么第 $i$ 名员工可以指导第 $j$ 名员工。请问有多少个有序对 $(i, j)$ 使得第 $i$ 名员工可以指导第 $j$ 名员工？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行给出两个整数 $N$ 和 $S$，分别表示员工的数量和技能的数量。

接下来的 $N$ 行描述每名员工掌握的技能。其中第 $i$ 行以一个整数 $C_i$ 开头，表示第 $i$ 名员工掌握的技能数量。然后在同一行中跟着 $C_i$ 个整数，其中第 $j$ 个整数 $A_{ij}$ 表示第 $i$ 名员工掌握了技能 $A_{ij}$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是满足条件的有序对 $(i, j)$ 的数量。

2
4 100
4 80 90 100 5
1 90
1 80
3 80 90 100
3 30
4 10 11 12 13
4 10 11 12 13
5 25 26 27 28 29

Case #1: 7
Case #2: 4

提示

在样例 #1 中：

• $(1, 2)$ 是有效对，因为员工 1 掌握技能 100（还有 5 和 80），而员工 2 不掌握。
• $(1, 3)$ 是有效对，因为员工 1 掌握技能 100（还有 5 和 90），而员工 3 不掌握。
• $(1, 4)$ 是有效对，因为员工 1 掌握技能 5，而员工 4 不掌握。
• $(2, 3)$ 是有效对，因为员工 2 掌握技能 90，而员工 3 不掌握。
• $(3, 2)$ 是有效对，因为员工 3 掌握技能 80，而员工 2 不掌握。
• $(4, 2)$ 是有效对，因为员工 4 掌握技能 100（还有 80），而员工 2 不掌握。
• $(4, 3)$ 是有效对，因为员工 4 掌握技能 100（还有 90），而员工 3 不掌握。

总共有 7 个有效对，因此答案为 7。

在样例 #2 中：

• $(1, 3)$ 是有效对，因为员工 1 掌握技能 10（还有 11、12 和 13），而员工 3 不掌握。
• $(2, 3)$ 是有效对，因为员工 2 掌握技能 10（还有 11、12 和 13），而员工 3 不掌握。
• $(3, 1)$ 是有效对，因为员工 3 掌握技能 28（还有 25、26、27 和 29），而员工 1 不掌握。
• $(3, 2)$ 是有效对，因为员工 3 掌握技能 27（还有 25、26、28 和 29），而员工 2 不掌握。

总共有 4 个有效对，因此答案为 4。

限制条件

$1 \le T \le 100$。

$1 \le S \le 1000$。

对于所有 $i$，$1 \le C_i \le 5$。

对于所有 $i, j$，$1 \le A_{ij} \le S$。

对于所有 $j \ne k$，$A_{ij} \ne A_{ik}$。

测试集 1（可见）

$2 \le N \le 500$。

测试集 2（隐藏）

$2 \le N \le 5 \times 10^4$。

翻译由 DeepSeek V4 Pro 完成