题目描述

Leopold 的朋友 Kate 喜欢石头，于是他决定送她一块金石作为礼物。石头共有 $S$ 种类型，编号为 $1$ 到 $S$，其中 $1$ 号是金石。城市中不同地点可以免费获得某些类型的石头。城市由 $N$ 个路口（编号 $1$ 到 $N$）和 $M$ 条连接不同路口对的双向街道组成。在每个路口，有零种或多种类型的石头无限量供应。

不幸的是，金石在任何路口都没有供应。幸运的是，Leopold 会一点魔法，他知道如何将一组石头组合并变成另一种石头。例如，他有一个配方可以用一块银石和两块大理石制成一块金石。他可以在某些路口收集这些石头（如果当地有供应），或者使用他的其他众多配方来生产这些石头中的任何一种。形式化地说，Leopold 有 $R$ 个配方，每个配方形式为 $(a_1, a_2, \ldots, a_k) \to b$，其中 $k \ge 1$。如果 Leopold 在某个路口收集了 $k$ 块类型分别为 $a_1, a_2, \ldots, a_k$ 的石头，他可以选择应用这个配方，将这些石头变成一块类型为 $b$ 的石头。

Leopold 喜欢解谜远胜于体力活动，因此他不想不必要地带着石头在城市里跑来跑去。携带一块石头穿过一条街道需要花费 $1$ 单位能量。Leopold 一次最多只能携带一块石头，但他可以在任何路口放下石头，并在以后任意时间捡起。

Leopold 至少需要花费多少能量才能生产出一块金石？

Leopold 非常害怕大数字。如果答案大于等于 $10^{12}$，则输出 $-1$。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含四个整数 $N$、$M$、$S$ 和 $R$，分别表示路口的数量、街道的数量、石头的种类数以及配方的数量。接下来的 $M$ 行描述城市的地图。其中第 $i$ 行包含两个不同的整数 $U_i$ 和 $V_i$，表示第 $i$ 条街道连接的两个路口。

随后的 $N$ 行描述每个路口可用的石头类型。第 $i$ 行以该路口可用的石头类型数量 $C_i$ 开头，后面跟着 $C_i$ 个互不相同的整数（范围在 $[2, S]$），列举这些石头类型。金石（编号 $1$）永远不会出现在任何路口的供应中。

每个测试用例的最后 $R$ 行描述 Leopold 的魔法配方。第 $i$ 行以该配方所需的原料石头数量 $K_i$ 开头，后面跟着 $K_i$ 个不一定互不相同的整数（范围在 $[2, S]$），列举所需原料的类型。该行以一个整数结尾（范围在 $[1, S]$），表示应用该配方后产出的石头类型。例如，3 6 5 6 3 表示一个配方需要两块类型 $6$ 的石头和一块类型 $5$ 的石头，产出类型 $3$ 的石头。

保证在每个测试用例中都能生产出一块金石。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是该测试用例的答案，即 Leopold 至少需要花费的能量值。如果答案大于等于 $10^{12}$，则输出 $-1$。

3
4 3 4 1
1 2
1 3
1 4
0
1 2
1 3
1 4
3 2 3 4 1
4 3 4 1
1 2
1 3
1 4
0
2 2 3
1 3
1 4
3 2 3 4 1
2 1 4 2
1 2
2 2 3
1 4
3 2 3 4 1
2 2 3 4

Case #1: 3
Case #2: 2
Case #3: 0

提示

在第一个测试用例中，达到最小能量的方式是：Leopold 分别在路口 $2$、$3$ 和 $4$ 收集石头 $2$、$3$ 和 $4$，将这些石头带到路口 $1$，然后使用他唯一的配方将这三块石头变成金石。这样，三块石头各自沿一条街道运输，因此总能量花费为 $3$。

前两个测试用例的唯一区别是：现在路口 $2$ 也供应石头 $3$。这时，最优方案是将一块类型 $4$ 的石头从路口 $4$ 运到路口 $2$（花费 $2$ 单位能量），然后在路口 $2$ 收集缺少的类型 $2$ 和 $3$ 的石头，使用唯一的配方生产金石。

在第三个测试用例中，Leopold 无需离开路口 $1$ 就能生产金石。首先，他收集类型 $2$ 和 $3$ 的石头，使用第二个配方生产类型 $4$ 的石头。第二步，他再次收集类型 $2$ 和 $3$ 的石头，与类型 $4$ 的石头组合，使用第一个配方生产金石。

限制条件

$1 \le T \le 100$。

$1 \le U_i, V_i \le N$，$U_i \ne V_i$。

$0 \le C_i < S$。

$1 \le K_i \le 3$。

每对路口之间最多有一条街道。

从任意路口出发，可以沿一系列街道到达任何其他路口。

保证可以生产出一块金石。

测试集 1

$2 \le N \le 50$。

$1 \le M \le 80$。

$2 \le S \le 50$。

$1 \le R \le 50$。

测试集 2

$2 \le N \le 300$。

$1 \le M \le 500$。

$2 \le S \le 300$。

$1 \le R \le 300$。

翻译由 DeepSeek V4 Pro 完成