题目描述

每年圣诞节，父母都会面临一个甜蜜的烦恼：为孩子们准备礼物。由于孩子们会互相比较收到的礼物，父母需要精心安排，确保没有一个孩子会嫉妒其他孩子的礼物。

在购物前，父母会向孩子们宣布一个固定的候选礼物集合，并说明每个孩子将获得这些候选礼物的一个子集。孩子们随后会向父母提出自己的快乐条件，这些条件通常是基于其他兄弟姐妹将获得的礼物来定义的。父母的目标是：在满足所有孩子条件的前提下，为每个孩子分配尽可能小的礼物子集。

每个孩子的条件总是一个逻辑与(conjunction)的形式：

我需要至少（a1 且 a2 且 ... 且 an）

其中，每个 $a_i$ 可以是以下四种类型之一：

1. [类型1] 一个固定的候选礼物子集（常量集合）；
2. [类型2] 一个兄弟姐妹的名字（表示该兄弟姐妹的礼物）；
3. [类型3] 两个 $a_i$（类型1或2）的共同部分（即两者共有的礼物）；
4. [类型4] 一个兄弟姐妹的名字，后跟 "except-for" 和一个固定的候选礼物子集（表示该兄弟姐妹的礼物排除某些特定礼物后的结果）。

示例

假设有三个孩子 $\\{X, Y, Z\\}$ 和三个候选礼物 $\\{a, b, c\\}$，他们的条件如下：

• $X$ 的条件：至少 $\\{a, b\\}$ 且 $Y$ 和 $Z$ 的共同礼物；
• $Y$ 的条件：至少 $Z$ 和 $\\{b, c\\}$ 的共同礼物；
• $Z$ 的条件：至少 $\\{a\\}$ 且 $X$ 的礼物排除 $\\{c\\}$。

此时，满足条件的最小礼物分配为：

• $X$：$\\{a, b\\}$
• $Y$：$\\{b\\}$
• $Z$：$\\{a, b\\}$

输入

输入包含 $T$ 个测试用例，第一行为测试用例数量 $T$。
每个测试用例的格式如下：

1. 第一行：两个整数 $n$（候选礼物数量，$1 \leq n \leq 1000$）和 $m$（孩子数量，$1 \leq m \leq 100$）；
2. 后续行：按孩子编号顺序（$1$ 到 $m$）描述每个孩子的条件：
   • 第一行：孩子的编号 $i$ 和其条件中的 $a_i$ 数量；
   • 后续行：每个 $a_i$ 的具体描述（每行一个 $a_i$），格式如下：
     • 类型1：-1 k g1 g2 ... gk（表示固定集合$\\{g1, g2, ..., gk\\}$）；
     • 类型2：-2 j（表示孩子 $j$ 的礼物）；
     • 类型3：-3 <ai1> <ai2>（表示 $ai1$ 和 $ai2$ 的共同部分，$ai1$ 和 $ai2$ 需为类型1或2）；
     • 类型4：-4 <ai1> <ai2>（表示 $ai1$ 的礼物排除 $ai2$ 中的礼物，$ai1$ 为类型2，$ai2$ 为类型1）。

输入样例

3
2 2
1 1
-1 1 1
2 1
-4 -2 1 -1 1 1
1 1
1 1
-3 -1 1 1 -1 1 1
3 3
1 2
-1 2 1 2
-3 -2 2 -2 3
2 1
-3 -2 3 -1 2 2 3
3 2
-1 1 1
-4 -2 1 -1 1 3

输出

按测试用例顺序输出结果，每个测试用例的输出为 $m$ 行（按孩子编号升序排列），每行格式为：

孩子编号 [礼物编号1 礼物编号2 ...]

若某孩子没有礼物，则仅输出其编号。

输出样例

1 1
2
1 1
1 1 2
2 2
3 1 2

题目来源

Taejon 2002