{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n\n\t\t\t\t\u003carticle class\u003d\"uoj-article top-buffer-md\"\u003e\n\t\t\t\u003ch3\u003e题目描述\u003c/h3\u003e\n\u003cp\u003e在 P 大学中,很多课程设立了小班课,学生可以自由根据需求选择小班课。当然,小班课的容量并不是无限的,并不是每个学生都能选上心仪的小班课。\u003c/p\u003e\n\u003cp\u003e本学期,共有 $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$ 门小班课。\u003c/p\u003e\n\u003cp\u003e学生们按照 $1\\sim n$ 的顺序进行选课,每次会选择优先度最高且未满的小班课,如果所有 $a_{i,1}\\sim a_{i,k_i}$ 都已满,那么该学生不会选择任何小班课。\u003c/p\u003e\n\u003cp\u003e现在给出每个学生的意向度序列,请重排学生的顺序,使得选上小班课的学生最多。并构造方案。\u003c/p\u003e\n\u003ch3\u003e输入格式\u003c/h3\u003e\n\u003cp\u003e从标准输入读入数据。\u003c/p\u003e\n\u003cp\u003e第一行一个正整数 $T(1\\leq T\\leq 500)$,表示数据组数。\u003c/p\u003e\n\u003cp\u003e对于每组数据,第一行两个正整数 $n,m(1\\leq n,m\\leq 500)$,即学生数量和小班课数量。\u003c/p\u003e\n\u003cp\u003e之后一行 $m$ 个非负整数 $b_i(0\\leq b_i\\leq 500)$,即每一门小班课的容量。\u003c/p\u003e\n\u003cp\u003e之后 $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)$,表示意向度序列。\u003c/p\u003e\n\u003ch3\u003e输出格式\u003c/h3\u003e\n\u003cp\u003e输出到标准输出。\u003c/p\u003e\n\u003cp\u003e对于每组数据,输出两行,第一行为一个整数 $ans$ 表示答案,之后一行 $n$ 个数,为一个 $1\\sim n$ 的排列,表示构造的方案。如果有多种方案,输出任意一种即可。\u003c/p\u003e\n\u003ch3\u003e样例\u003c/h3\u003e\n\u003ch4\u003e输入\u003c/h4\u003e\n\u003cpre\u003e\u003ccode class\u003d\"sh_plain\"\u003e3\n5 5\n1 1 1 1 1\n4 1 3 2 4\n1 5\n4 3 4 2 1\n2 3 5\n1 1\n5 3\n1 2 2\n2 1 2\n2 1 2\n2 1 3\n2 1 3\n2 1 3\n5 5\n1 1 1 1 1\n2 1 2\n2 5 4\n2 3 2\n2 4 3\n2 5 1\u003c/code\u003e\u003c/pre\u003e\n\u003ch4\u003e输出\u003c/h4\u003e\n\u003cpre\u003e\u003ccode class\u003d\"sh_plain\"\u003e5\n2 4 5 1 3\n5\n5 1 2 3 4\n5\n1 5 2 4 3\u003c/code\u003e\u003c/pre\u003e\n\u003ch3\u003e解释\u003c/h3\u003e\n\u003cp\u003e对于第一组数据,按照给定的方案,学生 $2$ 首先选择 $5$,然后学生 $4$ 选择 $3$,学生 $5$ 选择 $1$,学生 $1$ 尝试选择 $1,5$ 但都已满员,所以最终选择 $2$,学生 $3$ 尝试选择 $3$ 但已满员,所以最终选择 $4$。该组数据的方案不唯一,例如,$\\{2,5,4,3,1\\}$ 也是一个可行解。\u003c/p\u003e\n\u003cp\u003e对于第二组数据,$\\{1,2,3,4,5\\}$ \u003cstrong\u003e不\u003c/strong\u003e是一个可行解,如果这样构造,那么学生 $1,2,3,4$ 会分别选择 $1,2,3,3$,这时对于学生 $5$,$1,3$ 都已满员,因此无法选择任何课程。\u003c/p\u003e\n\t\t\u003c/article\u003e\n\t\t\t"}}]}