가르쳐 주기
면접 대비시간 제한40초메모리 제한1024 MB
각 직원은 최대 5개의 기술을 알고 있다. i가 알고 있지만 j는 모르는 기술이 있을 때 순서쌍 (i, j)의 개수를 구한다.
문제
구글에는 1번부터 N번까지 번호가 붙은 N명의 직원이 있다. 기술은 모두 S가지가 있으며 1번부터 S번까지 번호가 붙어 있다. 각 직원은 서로 다른 기술을 최대 5가지까지 알고 있다.
i번 직원이 아는 기술 중 j번 직원이 모르는 기술이 하나라도 있으면 i번 직원은 j번 직원을 멘토링할 수 있다. i번 직원이 j번 직원을 멘토링할 수 있는 순서쌍 (i, j)는 모두 몇 개인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 직원의 수 N과 기술의 수 S가 주어진다.
다음 N개의 줄은 각 직원이 아는 기술을 나타낸다. 이 중 i번째 줄은 i번 직원이 아는 기술의 수 Ci로 시작한다. 이어서 같은 줄에 Ci개의 정수가 주어진다. 이 정수 중 j번째 정수 Aij는 i번 직원이 기술 Aij를 안다는 뜻이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 줄을 하나씩 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 i번 직원이 j번 직원을 멘토링할 수 있는 순서쌍 (i, j)의 수이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ S ≤ 1000.
- 모든 i에 대해 1 ≤ Ci ≤ 5.
- 모든 i, j에 대해 1 ≤ Aij ≤ S.
- j ≠ k이면 Aij ≠ Aik.