소셜 네트워크 백신 접종

보건 정책 결정은 흥미로운 계산 문제로 이어지곤 하며, 그중 하나가 백신 접종이다. 접종 여부를 각 개인에게 맡기는 방식은 접종한 사람만 이익을 본다고 가정한다. 하지만 실제로는 그렇지 않다. 접종한 사람은 병에 걸리지도, 남에게 옮기지도 않으므로 주변 사람들까지 크게 보호한다. 따라서 사회 전체를 잘 보호하려면 누구에게 접종할지를 신중하게 고르는 것이 이상적이다.

이를 다음과 같이 단순하게 모형화한다. 개인과 그들의 친구 관계로 이루어진 소셜 네트워크(그래프)가 주어진다. 누군가 병에 걸리면 그 사람은 접종하지 않은 모든 친구에게 병을 옮기고, 그 친구들도 같은 방식으로 병을 퍼뜨린다. 접종한 사람은 절대 병에 걸리지 않는다. 우리에게는 백신 $D$개가 있어 $D$명에게 접종할 수 있다. 접종을 마친 뒤, 최악의 경우를 가정하여 병이 어느 한 사람에게서 발생한다고 하자. 이 발병 지점은 결국 병에 걸리는 사람 수가 최대가 되도록 정해진다. 우리의 목표는, 이 최악의 가정 아래 결국 병에 걸리는 사람 수가 가능한 한 작아지도록 접종할 $D$명을 고르는 것이다. 그 최솟값을 구하라.

첫 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 두 정수 $n$, $D$가 주어진다. $1 \le n \le 30$은 네트워크에 있는 사람 수이고, $0 \le D \le 6$은 가지고 있는 백신 개수이다. 사람에게는 $1$번부터 $n$번까지 번호가 매겨져 있다.

그다음 $n$개의 줄이 주어지며, $i$번째 줄에는 $i$번 사람의 모든 친구가 공백으로 구분되어 나열된다. 친구 관계는 반사적이고 대칭적이다. 즉, 모든 사람은 최소한 자기 자신을 친구로 가지며, $i$가 $j$의 친구이면 $j$도 $i$의 친구이다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작한다. 그다음 줄에는 접종 대상을 최적으로 골랐을 때 최악의 경우에 병에 걸리는 사람 수를 출력한다. 연속한 두 데이터 집합 사이에는 빈 줄을 하나 넣는다.