P16739 [GKS 2019 #F] Teach Me

在 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)$ 的数量。

在样例 #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 完成