Transparency

You must audit a factory that produces several products. Each product follows its own taxation rules. Working out which rules apply is hard, because the products are difficult to tell apart. Your job is to check whether the factory is completely transparent in its production process, that is, whether it can produce two different products that look the same when lowercase letters are ignored.

Final products are strings of uppercase letters ('A' to 'Z') and lowercase letters ('a' to 'z'). Two final products are indistinguishable if they are equal after all lowercase letters are removed. For example, WabXYcz is indistinguishable from gWXfbY, since removing the lowercase letters leaves WXY in both.

A factory is modelled as a set of stations $S$, a set of directed transition edges $T$ with labels, an initial station $s_0$, and a set of packaging stations $P$. The initial station is in the set of stations, so $s_0 \in S$, and $P \subseteq S$. A transition edge is a 3-tuple $(s_1, \sigma, s_2)$, where $s_1, s_2 \in S$ and $\sigma$ is an uppercase or lowercase letter. The edge means that if production is at station $s_1$, appending $\sigma$ to the product leaves it at station $s_2$. In other words, there is an edge from $s_1$ to $s_2$ labelled $\sigma$.

A product can be produced if, starting at $s_0$, there is a sequence of edges that ends at a station in $P$ and whose labels, concatenated in order, form the product. The sequence can be empty if $s_0 \in P$. For example, the first sample factory can produce AF, FAFB, AbFFAd, and AdydAd. This list is not exhaustive. Each transition can be used an unlimited number of times.

For each station and letter, there is at most one outgoing edge labelled with that letter. That is, $(s_1, \sigma, s_2), (s_1, \sigma, s_3) \in T$ implies $s_2 = s_3$. A transition may return to the same station, so $(s_1, \sigma, s_1) \in T$ is allowed.

Given a factory design, determine whether it can produce two distinct but indistinguishable products. If such a pair exists, report the smallest possible sum of the lengths of the two strings in a pair. If no such pair exists, print $-1$.

The first line has three integers $s$ ($1 \le s \le 50$), $p$ ($1 \le p \le s$), and $t$ ($1 \le t \le 52 \cdot s$): the number of stations, the number of packaging stations, and the number of transitions. Stations are numbered 1 to $s$.

Each of the next $p$ lines contains one integer $i$ ($1 \le i \le s$), a packaging station. All values are distinct.

Each of the next $t$ lines has the form $s_1 \sigma s_2$, meaning a transition from station $s_1$ to station $s_2$ labelled with the letter $\sigma$, where $\sigma$ is an uppercase or lowercase letter. The initial station is always station 1. No two transitions leave the same station with the same letter.

Output one integer. If no pair of distinct, indistinguishable products exists, print $-1$. Otherwise, print the smallest value of $|a|+|b|$, where $a$ and $b$ are strings forming such a pair.

The factory design from the first sample input. Packaging stations are drawn with double circles.