Social Network Vaccinations

Time limit2sMemory limit128 MB

Summary

Given a graph with n at most 30 and D at most 6, choose D vertices to vaccinate so that the largest connected component remaining is as small as possible.

Level: Medium7 of 10
Topics: Graph, Brute force, DFS, Combinatorics
Solved: No attempts yet

Problem

Health-care policy decisions lead to many interesting computational questions, and one of them concerns vaccinations. Leaving the decision to each individual assumes that only the vaccinated person benefits. That is far from the truth: a vaccinated person can neither catch nor transmit the disease, so they also help protect everyone around them. From society's point of view, it is therefore best to choose carefully who gets vaccinated.

We model this as follows. We are given a social network (a graph) of individuals and their friendships. Whenever someone gets sick, they infect all of their unvaccinated friends, who then spread the disease in the same way. A vaccinated person never gets sick. We have $D$ doses of the vaccine, so we may vaccinate $D$ individuals. After vaccinating, we pessimistically assume that the disease breaks out at a single individual, and that this starting point is chosen so as to maximize the number of people who eventually get sick. Our goal is to choose the $D$ individuals to vaccinate so that this worst-case number of sick people is as small as possible. Report that minimum.

Input

The first line contains the number $K$ of data sets. Then follow the $K$ data sets, each in the following form.

The first line of a data set contains two integers $n$ and $D$ , where $1 \le n \le 30$ is the number of people in the network and $0 \le D \le 6$ is the number of vaccine doses available. People are numbered from $1$ to $n$ .

This is followed by $n$ lines; the $i$ -th of them lists all friends of person $i$ , separated by spaces. Friendship is reflexive and symmetric: everyone is at least their own friend, and if $i$ is a friend of $j$ , then $j$ is a friend of $i$ .

Output

For each data set, first print Data Set x: on a line by itself, where $x$ is the data set's number (starting from $1$ ). On the next line, print the number of people who get sick in the worst case when the vaccinated individuals are chosen optimally. Put one blank line between consecutive data sets.

Examples4

Example 1

Input

1
11 2
1 2 3 4
1 4 2 3
1 2 3 4 6 5 7
7 1 2 6 5 3 4
3 4 5 6 7 8 9
3 4 5 6 7 8 9
3 4 5 6 7 8 9
5 6 7 8 9 10 11
6 5 11 10 9 8 7
8 9 10 11
9 8 11 10

Expected output

Data Set 1:
7

Example 2
Input
```
1
1 0
1
```
Expected output
```
Data Set 1:
1
```
Example 3
Input
```
1
3 6
1 2 3
2 1 3
3 1 2
```
Expected output
```
Data Set 1:
0
```

Example 4

Input

Expected output

Data Set 1:
3