Description

Problem description: Assume a question bank contains $n$ questions. Each question is labeled with one or more types. We need to select $m$ questions from the bank to form an exam paper, and the paper must include the specified numbers of questions of each type. Design an algorithm that meets this requirement.

Programming task: Given the selection requirements, compute a selection plan that satisfies them.

Input Format

The first line contains two positive integers $k$ and $n$. Here, $k$ is the total number of types in the question bank, and $n$ is the total number of questions.

The second line contains $k$ positive integers; the $i$-th integer is the required count of type $i$ questions. The sum of these $k$ numbers is the total number of questions to select, $m$.

Each of the next $n$ lines gives the type information for one question. The first positive integer $p$ indicates that the question belongs to $p$ types, followed by $p$ integers that are the type IDs of the question.

Output Format

Output $k$ lines. On the $i$-th line, print i: followed by the indices of the selected questions of type $i$. If multiple valid solutions exist, output any one of them. If no solution exists, output No Solution!.

3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3

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

Hint

$2 \leq k \leq 20$, $k \leq n \leq 10^3$.

Thanks to @PhoenixEclipse for providing the SPJ.

Translated by ChatGPT 5