Problem Library

Problem Source

Network Flow 24 Problems

Problem Description

Suppose a problem library contains $n$ problems. Each problem is tagged with one or more categories. The same problem may belong to several categories. Now you must pick $m$ problems from the library to form an exam paper, and the paper must contain the required number of problems from each specified category. Design an algorithm that produces a paper satisfying the requirements.

Input Format

The first line contains two integers $k, n(1\leq n\leq 1000, 2\leq k\leq 20, k\leq n)$. $k$ is the total number of categories in the library, $n$ is the total number of problems. The second line contains $k$ positive integers; the $i$-th positive integer is the number of type-$i$ problems to be selected. The sum of these $k$ numbers is the total number $m$ of problems to be selected.

The following $n$ lines give the category information of each problem in the library. The first positive integer $p$ on each line indicates that the problem may belong to $p$ categories, and the following $p$ numbers are the category numbers to which the problem belongs.

Output Format

For the $i$-th category, output i: followed by the indices of the problems of type $i$. If there are multiple valid schemes, output any one of them. If the problem has no solution, output No Solution!.

Note: if the number of problems of a category is $0$, you still need to put a space after i:.

Sample Input

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

Sample Output

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

Hint

• This is a classic bipartite-matching / maximum-flow modeling problem: connect a source to each category with capacity equal to the required count, each category to the problems that belong to it with capacity 1, and each problem to the sink with capacity 1. If the maximum flow equals the total required $m$, the matching tells you which problems fill which categories.