P16051 [ICPC 2022 NAC] Transparency

你必须对一家生产多种产品的工厂进行审计。每种产品都有其自身的税收规则和法规。不幸的是，决定哪些规则适用于哪种产品并不容易，因为产品之间可能难以区分。你的任务是通过判断工厂是否能够生产出两种不同但无法区分的产品，来调查该工厂在生产过程中是否完全 **透明**。 最终产品由大写字母（`A`–`Z`）和小写字母（`a`–`z`）组成的序列表示。如果两种产品在移除所有小写字母后得到的字符串相同，则它们彼此无法区分。例如，`WabXYcz` 与 `gWXfbY` 无法区分，因为移除所有小写字母后，两者都剩下 `WXY`。 工厂的模型包括：一组站点 $S$，一组带标记的有向转移边 $T$，一个初始站点 $s_0$，以及一组包装站点 $P$。初始站点属于站点集合，即 $s_0 \in S$，包装站点集合是 $S$ 的子集，即 $P \subseteq S$。一条转移边由一个三元组 $(s_1, \sigma, s_2)$ 定义，其中 $s_1, s_2 \in S$ 是站点，$\sigma$ 是一个大写或小写字母。若 $T$ 中存在转移 $(s_1, \sigma, s_2)$，则表示在生产某个产品的过程中，如果当前处于站点 $s_1$，那么将 $\sigma$ 附加到产品末尾后，将到达站点 $s_2$。也就是说，存在一条从站点 $s_1$ 到站点 $s_2$、标记为 $\sigma$ 的有向边。 如果从初始站点 $s_0$ 出发，存在一条边序列，其终点位于某个包装站点 $P$ 中，并且将这些边的标记按顺序拼接起来就得到了该产品，那么该产品就可以由工厂生产出来。如果 $s_0 \in P$，则边序列可以为空。例如，在第一个样例输入对应的工厂（如下图所示）中，可以生产出以下字符串：`AF`、`FAFB`、`AbFFAd`、`AdydAd`。注意，这些并不是全部可生产的字符串。 每条生产转移边可以被无限次使用来生产产品。保证对于每个站点 $s$ 和每个字母 $\sigma$，从站点 $s$ 出发标记为 $\sigma$ 的有向边至多只有一条。即，若 $(s_1, \sigma, s_2), (s_1, \sigma, s_3) \in T$，则必有 $s_2 = s_3$。允许转移边指向同一个站点，即允许 $(s_1, \sigma, s_1) \in T$。 给定一个工厂的设计，请判断该工厂是否能够生产出两个不同但无法区分的产品。如果存在这样的一对产品，请报告使得这对产品长度之和最小的那一对，输出该长度和。如果不存在这样的产品对，则输出 $-1$。 :::align{center}  第一个样例输入中的工厂设计图。包装站点用双圆圈标记。 :::

输入的第一行包含三个整数 $s$（$1 \le s \le 50$）、$p$（$1 \le p \le s$）和 $t$（$1 \le t \le 52 \cdot s$），其中 $s$ 是站点的数量，$p$ 是包装站点的数量，$t$ 是转移边的数量。站点编号为 $1$ 到 $s$。 接下来的 $p$ 行，每行包含一个整数 $i$（$1 \le i \le s$）。这些是包装站点。所有 $i$ 的值互不相同。 接下来的 $t$ 行，每行格式如下： $$s_1\quad \sigma\quad s_2$$ 其中 $s_1$ 和 $s_2$（$1 \le s_1, s_2 \le s$）是站点，$\sigma$ 是一个字符，可以是大写字母或小写字母。这些行表示转移边。初始站点始终为站点 $1$。保证不会出现从同一状态出发、标记为相同字符的两条不同转移边。

输出一行一个整数。如果不存在两个不同但无法区分的产品，则输出 $-1$。如果存在这样的一对产品，则输出最小的长度和 $|a| + |b|$，其中 $a$ 和 $b$ 是两个不同但无法区分的产品字符串。

翻译由 DeepSeek V3.2 完成