题目描述

Here at Google we love teaching new skills to each other! There are $N$ employees at Google, numbered from $1$ to $N$. There are a total of $S$ different skills, numbered from $1$ to $S$. Each employee knows up to 5 different skills.

The i-th employee can mentor the j-th employee if there is a skill that the i-th employee knows that the j-th employee does not know. How many ordered pairs $(i, j)$ are there where the i-th employee can mentor the j-th employee?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case gives the two integers $N$ and $S$, which are the number of employees and the number of skills respectively.

The next $N$ lines describe the skills that each employee knows. The i-th of these lines begins with an integer $C_i$ which is the number of skills the i-th employee knows. Then, $C_i$ integers follow on the same line. The j-th of these integers is $A_{ij}$ indicating that the i-th employee knows the skill $A_{ij}$.

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of ordered pairs $(i, j)$ where the i-th employee can mentor the j-th employee.

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

提示

In Sample case #1:

• (1, 2) is a valid pair since employee 1 knows the skill 100 (also 5 and 80), while employee 2 does not.
• (1, 3) is a valid pair since employee 1 knows the skill 100 (also 5 and 90), while employee 3 does not.
• (1, 4) is a valid pair since employee 1 knows the skill 5, while employee 4 does not.
• (2, 3) is a valid pair since employee 2 knows the skill 90, while employee 3 does not.
• (3, 2) is a valid pair since employee 3 knows the skill 80, while employee 2 does not.
• (4, 2) is a valid pair since employee 4 knows the skill 100 (also 80), while employee 2 does not.
• (4, 3) is a valid pair since employee 4 knows the skill 100 (also 90), while employee 3 does not.

In total, there are 7 valid pairs, so the answer is 7.

In Sample case #2:

• (1, 3) is a valid pair since employee 1 knows the skill 10 (also 11, 12 and 13), while employee 3 does not.
• (2, 3) is a valid pair since employee 2 knows the skill 10 (also 11, 12 and 13), while employee 3 does not.
• (3, 1) is a valid pair since employee 3 knows the skill 28 (also 25, 26, 27 and 29), while employee 1 does not.
• (3, 2) is a valid pair since employee 3 knows the skill 27 (also 25, 26, 28 and 29), while employee 2 does not.

In total, there are 4 valid pairs, so the answer is 4.

Limits

$1 \le T \le 100$.

$1 \le S \le 1000$.

$1 \le C_i \le 5$ for all i.

$1 \le A_{ij} \le S$ for all i and j.

$A_{ij} \ne A_{ik}$ for all $j \ne k$.

Test set 1 (Visible)

$2 \le N \le 500$.

Test set 2 (Hidden)

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