Oh no! Agent Ω realized that she needs much larger teams than she originally thought. Your algorithm from the previous question will be too slow. In fact, any classical algorithm is going to be too slow to find a perfect answer. As such, you just need to find the best answer that you can
– and print out the full answer.
For this problem, you will be graded on how close your answer comes to the correct answer. For every test case, you should return AN answer (timing out will result in no points for the given test case, but a poor answer may get some); the quality of your answer will determine how much credit you receive on the test case.
You are allowed to use a timing mechanism to decide when to stop searching and print an answer. C++ programs get 4 seconds of runtime and Python programs get 10 seconds.
Note: Full credit for this problem is 18 points (out of a max of 30). Anything beyond that is extra credit.
Input Format
The first line has two values, N and K.
N represents the number of potential crew members available (numbered 0 through N - 1), and K is the number of distinct skills that need to be included (numbered 0 through K - 1).
The next N pairs of lines each provide information about a single person.
The first line for person i indicates the number of skills that person has (Pi), and the second line has Pi values indicating the specific skill IDs (we’re not using names this time to keep it simple).
Constraints
N == 1000
500 ≤ K ≤ 1200
8 ≤ Pi ≤ 200
Output Format
You should output S, the size of the smallest team you could find (the minimum number of agents). Followed on the next line by the list of agents to be included.
Example 0
Sample Input
5
3
1 2
2 4
Sample Output
2
0 2
Explanation
There are three agents to choose from in the example input, and five total skills. These agents are then presented in order. Agent 0 has 2 skills: 1 and 3. Agent 1 has 3 skills: 0, 1, and 2. Agent 2 also has 3 skills: 0, 2, and 4.
The output provided indicates that two agents are chosen for the team, agent 0 and agent 2. Since these two agents comprise the full set of skills, 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 agents were included in the answer, it would still be correct (since all of the skills would be covered), but it would not be minimal so it would receive fewer points.
