Dakota has received useful information from Millennium about Queen Mellifluous’ plans. She now knows what other alien artifacts are on Earth and how to put them together into an effective defense. But will she have time to collect all of the artifacts she needs? Given the set properties associated with each artifact, you must figure out the fewest number of artfacts that can be collected such that all of the properties are represented.
While this problem may seem identical to the one solved by Dr. Niacal (and Dakota did find his algorithm when she seized his stronghold!), there are two main differences: The instances here are much larger so you will need to come up with a heuristic to solve it AND you must output the specific artifiact IDs used so that they can be verified.
Input Format
The first line has two values, N and K.
represents the number of artifacts available (numbered 0 through N-1), and K is the number of distinct properties that need to be included (numbered 0 through K-1).
The next N pairs of lines each provide information about a single artifact.
The first line for artifact i indicates the number of properties that artifact has (Pi), and the second line has Pi values indicating the specific properties.
Constraints
N== 1000
500 ≤ K ≤ 1200
8 ≤ Pi ≤ 200
Output Format
You should output two lines. The first line indicates S, the size of the best solution you could find (the minimum number of artifacts). The next line has S space-separated values indicating the IDs of the artifacts to collect.
Example Input
3 5
2
1 3
3
0 1 2
3
0 2 4
Example Output
2
0 2
Example Explanation
There are three artifacts to choose from in the example input, and five total properties. These artifacts are then presented in order. Artifact 0 has 2 properties: 1 and 3. Artifact 1 has 3 properties: 0, 1, and 2. Artifact 2 also has 3 properties: 0, 2, and 4.
The output provided indicates that two artifacts are choosen, artifact 0 and artifact 2. Since these two artifacts comprise the full set of properties, this answer would be deemed “correct” and would receive points. Given that it is also the minimal answer, it would receive the maximum number of points. If, instead, all three artifacts were included in the answer, it would still be correct (since all of the properties would be included), but it would not be minimal so it would receive fewer points.