#6006. 「网络流 24 题」试题库

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

假设一个试题库中有 nn 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 mm 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

输入格式

11 行有 22 个正整数 kknnkk 表示题库中试题类型总数,nn 表示题库中试题总数。第 22 行有 kk 个正整数,第 ii 个正整数表示要选出的类型 ii 的题数。这 kk 个数相加就是要选出的总题数 mm

接下来的 nn 行给出了题库中每个试题的类型信息。每行的第 11 个正整数 pp 表明该题可以属于 pp 类,接着的 pp 个数是该题所属的类型号。

输出格式

ii 行输出 i: 后接类型 ii 的题号。如果有多个满足要求的方案,只要输出一个方案。如果问题无解,则输出 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

数据范围与提示

2k20,kn10002 \leq k \leq 20, k \leq n \leq 1000