Teach Me
면접 대비시간 제한40초메모리 제한1024 MB
각 직원이 최대 5개의 기술을 알 때, 한 직원이 다른 직원에게 없는 기술을 가진 순서쌍의 개수를 센다.
문제
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 Ci which is the number of skills the i-th employee knows. Then, Ci integers follow on the same line. The j-th of these integers is Aij indicating that the i-th employee knows the skill Aij.
출력
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.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ S ≤ 1000.
- 1 ≤ Ci ≤ 5 for all i.
- 1 ≤ Aij ≤ S for all i and j.
- Aij ≠ Aik for all j ≠ k.