P13284 [GCJ 2013 Qualification] Treasure

按照一张古老的地图，你偶然发现了臭名昭著的海盗 Larry 的秘密宝藏！ 宝藏由 $N$ 个上锁的箱子组成，每个箱子只能用某一种特定类型的钥匙打开。而且，每把钥匙一旦用来打开一个箱子，就不能再重复使用。当然，每个箱子里都藏有大量宝藏，同时你还可能找到一把或多把可以用来打开其他箱子的钥匙。一个箱子里可能包含多把相同类型的钥匙，并且你可以持有任意数量的钥匙。 你一开始就至少拥有一把钥匙，你的地图还标明了各个箱子里可以找到哪些钥匙。已知所有这些信息，你能否想出一种方法，打开所有的箱子？ 例如，假设宝藏由下表所示的四个箱子组成，并且你起始时恰好有一把类型为 $1$ 的钥匙： | 箱子编号 | 打开所需钥匙类型 | 箱内钥匙类型 | | :---: | :---: | :---: | | 1 | 1 | 无 | | 2 | 1 | 1, 3 | | 3 | 2 | 无 | | 4 | 3 | 2 | 在这个例子中，如果你按照 $2$、$1$、$4$、$3$ 的顺序打开箱子，就能全部打开。如果你一开始就打开第 $1$ 号箱子，那么你会用光唯一的一把钥匙，接下来就无法继续了。

输入的第一行为测试用例数 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行为两个正整数 $K$ 和 $N$，分别表示你起始时拥有的钥匙数量以及需要打开的箱子数量。 接下来一行包含 $K$ 个整数，表示你起始时拥有的钥匙类型。 之后有 $N$ 行，每行描述一个箱子。每行首先是两个整数 $T_i$ 和 $K_i$，分别表示打开该箱子所需的钥匙类型，以及箱子内钥匙的数量。接下来是 $K_i$ 个整数，表示箱子内包含的钥匙类型。

对于每个测试用例，输出一行 `"Case #x: C_1 C_2 ... C_N"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$C_i$ 表示你应当打开的第 $i$ 个箱子的编号（从 $1$ 开始）。 如果存在多种打开所有箱子的方式，选择**字典序最小**的一种。也就是说，优先让 $C_1$ 尽可能小，若 $C_1$ 有多种选择，则让 $C_2$ 尽可能小，依此类推。 如果无法打开所有箱子，则输出一行 `"Case #x: IMPOSSIBLE"`。

**限制条件** - $1 \leq T \leq 25$ - $1 \leq K$ - 所有钥匙类型均为 $1$ 到 $200$ 之间的整数 **小数据集（20 分，测试集 1 - 可见）** - $1 \leq N \leq 20$ - 每个测试用例中，所有钥匙总数不超过 $40$ **大数据集（60 分，测试集 2 - 隐藏）** - $1 \leq N \leq 200$ - 每个测试用例中，所有钥匙总数不超过 $400$ 翻译由 ChatGPT-4.1 完成。