시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 207 85 55 40.146%

문제

진욱이는 새로운 소셜 네트워킹 회사를 만들기로 결심했다. 하지만 기존의 페이스북 이나 트위터 같이 인기있는 소셜 네트워크 서비스는 이미 수십억의 사용자를 가지고 있고, 진욱이는 이들과 경쟁에서 승리하는 유일한 방법은 다른 소셜 네트워크가 가지고 있지 않은 새로운 기능을 포함하는 것이라 생각했다.

진욱이는 광고주에게 값싼 방법으로 광고비를 청구할 방법을 생각해냈다. 광고주는 어떤 사용자의 담벼락에 광고를 나타낼지 고르고 선택된 사용자의 광고비만 지불하면 된다. 광고가 사용자들의 담벼락에 게시되었을때, 사용자의 친구들 모두 그 광고를 볼 수 있다. 이러한 방식으로 더 많은 사용자들에 광고를 알리기 위해 광고주는 적은 수의 광고비용만 지불하면 된다.

해빈이는 진욱이의 소셜 네트워크에 광고를 게시하고 싶어한다. 해빈이는 이미 사용자들의 "친구 목록" 을 가지고 있으며 이 그룹의 모든 사용자들이 광고를 보기 위해서 해빈이가 특정 사용자들의 담벼락에 게시해야 하는 최소의 광고 수를 구하여라.

진욱이의 소셜 네트워크에서는 A와 B가 친구이면 B도 A와 친구이다.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다. 첫째 줄은 테스트 케이스를 나타낸다. 각각의 케이스마다 전체 사용자의 수 n (1 ≤ n ≤ 20) 이 주어진다. 다음 n개의 줄에는 친구의 목록이 입력으로 주어지는데 각각의 줄은 친구의 수 d (0 ≤ d < n) 가 먼저 입력으로 주어지고 뒤이어 d개의 친구 번호가 주어진다. i번째 줄은 i번째 사용자를 뜻하며 자기 자신이 친구일 수는 없다.

출력

각각의 케이스 마다 모든 사용자들이 광고를 볼수 있도록 해빈이가 게시하여야 하는 최소의 광고 수를 출력한다.

예제 입력

2
5
4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4
5
2 4 5
2 3 5
1 2
2 1 5
3 1 2 4

예제 출력

1
2

힌트