QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[0]

# 8759. 小班课

Statistics

题目描述

在 P 大学中,很多课程设立了小班课,学生可以自由根据需求选择小班课。当然,小班课的容量并不是无限的,并不是每个学生都能选上心仪的小班课。

本学期,共有 n 名同学报名了 A 课程,该课程共设立了 m 门小班课,第 i 门小班课有容量 bi。第 i 名学生对小班课有一个意向度序列 ai,1ai,ki,其中 ai,1 表示意向度最高的课程,ai,ki 表示意向度最低的课程。如果一门小班课 j 不在这个序列里,那么说明学生 i 无法参加第 j 门小班课。

学生们按照 1n 的顺序进行选课,每次会选择优先度最高且未满的小班课,如果所有 ai,1ai,ki 都已满,那么该学生不会选择任何小班课。

现在给出每个学生的意向度序列,请重排学生的顺序,使得选上小班课的学生最多。并构造方案。

输入格式

从标准输入读入数据。

第一行一个正整数 T(1T500),表示数据组数。

对于每组数据,第一行两个正整数 n,m(1n,m500),即学生数量和小班课数量。

之后一行 m 个非负整数 bi(0bi500),即每一门小班课的容量。

之后 n 行,每行首先是一个非负整数 ki(0kim),之后是 ki 个两两不同的正整数 ai,1ai,ki(1ai,jm),表示意向度序列。

输出格式

输出到标准输出。

对于每组数据,输出两行,第一行为一个整数 ans 表示答案,之后一行 n 个数,为一个 1n 的排列,表示构造的方案。如果有多种方案,输出任意一种即可。

样例

输入

3
5 5
1 1 1 1 1
4 1 3 2 4
1 5
4 3 4 2 1
2 3 5
1 1
5 3
1 2 2
2 1 2
2 1 2
2 1 3
2 1 3
2 1 3
5 5
1 1 1 1 1
2 1 2
2 5 4
2 3 2
2 4 3
2 5 1

输出

5
2 4 5 1 3
5
5 1 2 3 4
5
1 5 2 4 3

解释

对于第一组数据,按照给定的方案,学生 2 首先选择 5,然后学生 4 选择 3,学生 5 选择 1,学生 1 尝试选择 1,5 但都已满员,所以最终选择 2,学生 3 尝试选择 3 但已满员,所以最终选择 4。该组数据的方案不唯一,例如,{2,5,4,3,1} 也是一个可行解。

对于第二组数据,{1,2,3,4,5} 是一个可行解,如果这样构造,那么学生 1,2,3,4 会分别选择 1,2,3,3,这时对于学生 51,3 都已满员,因此无法选择任何课程。