1284 : 小班课

Description

在 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}\) 都已满，那么该学生不会选择任何小班课。

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

Input

第一行一个正整数 \(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)\)，表示意向度序列。

Output

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

Sample

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

Hint

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

Source

Author

THU