你需要审计一家生产多种产品的工厂。每种产品都受其自身的税务规则和法规约束。不幸的是，由于很难将产品彼此区分开来，因此确定哪些规则适用于某种产品并不容易。你的工作是通过确定工厂是否能够生产出两种彼此无法区分的不同产品，来调查该工厂的生产过程是否完全透明。

最终产品由大写字母（‘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$ 是一个大写或小写字母。转换 $(s_1, \sigma, s_2) \in T$ 的存在意味着在生产某种产品时，如果我们处于站点 $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$。

输入格式

输入的第一行包含三个整数 $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 \ \sigma \ s_2$

其中 $s_1$ 和 $s_2$ ($1 \le s_1, s_2 \le s$) 是站点，$\sigma$ 是一个大写或小写字母。这些是转换。初始站点始终为站点 $1$。永远不会有两个从同一状态出发且标签相同的转换。

输出格式

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

样例

样例输入 1

4 1 8
3
1 F 1
1 A 2
2 b 1
2 F 3
2 d 3
3 B 3
3 y 4
4 d 1

样例输出 1

10

样例输入 2

4 1 8
3
1 F 1
1 A 2
2 b 1
2 F 3
2 d 3
3 B 3
3 y 4
4 d 4

样例输出 2

-1

样例输入 3

5 2 5
1
5
1 i 2
2 c 3
3 p 4
4 c 1
1 I 5

样例输出 3

4