P13358 [GDCPC 2024] 小班课

数据、标程、题解等资源的获取：

在 P 大学中，很多课程设立了小班课，学生可以自由根据需求选择小班课。当然，小班课的容量并不是无限的，并不是每个学生都能选上心仪的小班课。 本学期，共有 $n$ 名同学报名了 A 课程，该课程共设立了 $m$ 门小班课，第 $i$ 门小班课有容量 $b_i$。第 $i$ 名学生对小班课有一个意向度序列 $a_{i,1}\sim a_{i,k_i}$，其中 $a_{i,1}$ 表示意向度最高的课程，$a_{i,k_i}$ 表示意向度最低的课程。如果一门小班课 $j$ 不在这个序列里，那么说明学生 $i$ 无法参加第 $j$ 门小班课。 学生们按照 $1\sim n$ 的顺序进行选课，每次会选择优先度最高且未满的小班课，如果所有 $a_{i,1}\sim a_{i,k_i}$ 都已满，那么该学生不会选择任何小班课。 现在给出每个学生的意向度序列，请重排学生的顺序，使得选上小班课的学生最多。并构造方案。

第一行一个正整数 $T(1\leq T\leq 500)$，表示数据组数。 对于每组数据，第一行两个正整数 $n,m(1\leq n,m\leq 500)$，即学生数量和小班课数量。 之后一行 $m$ 个非负整数 $b_i(0\leq b_i\leq 500)$，即每一门小班课的容量。 之后 $n$ 行，每行首先是一个非负整数 $k_i(0\leq k_i\leq m)$，之后是 $k_i$ 个两两不同的正整数 $a_{i,1}\sim a_{i,k_i}(1\leq a_{i,j}\leq m)$，表示意向度序列。

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

对于第一组数据，按照给定的方案，学生 $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$，这时对于学生 $5$，$1,3$ 都已满员，因此无法选择任何课程。