투명성 감사

감사해야 할 공장은 여러 제품을 만든다. 각 제품에는 고유한 과세 규칙이 있다. 제품끼리 구별하기 어려워 어떤 규칙이 적용되는지 바로 알기 힘들다. 당신의 일은 이 공장이 생산 과정을 완전히 투명하게 운영하는지 조사하는 것이다. 구체적으로, 소문자를 무시했을 때 같아 보이는 서로 다른 두 제품을 공장이 만들 수 있는지 판단한다.

최종 제품은 대문자 영문자('A'부터 'Z')와 소문자 영문자('a'부터 'z')로 이루어진 문자열이다. 두 최종 제품은 소문자를 모두 제거한 뒤 같으면 구별되지 않는다. 예를 들어 WabXYcz와 gWXfbY는 소문자를 제거하면 둘 다 WXY가 남으므로 구별되지 않는다.

공장은 스테이션 집합 $S$, 라벨이 붙은 방향 전이 간선 집합 $T$, 초기 스테이션 $s_0$, 포장 스테이션 집합 $P$로 모델링한다. 초기 스테이션은 $s_0 \in S$이고, 포장 스테이션 집합은 $P \subseteq S$이다. 전이 간선은 3-튜플 $(s_1, \sigma, s_2)$로 정의되며, 여기서 $s_1, s_2 \in S$이고 $\sigma$는 대문자 또는 소문자 영문자이다. 이 간선은 생산이 스테이션 $s_1$에 있을 때 $\sigma$를 붙이면 스테이션 $s_2$에 머문다는 뜻이다. 즉 $s_1$에서 $s_2$로 가는 라벨 $\sigma$의 간선이 있다.

$s_0$에서 시작해 간선을 따라가고, 간선의 라벨을 순서대로 이어 붙인 결과가 제품이 되며, 마지막 스테이션이 $P$에 속하면 그 제품을 생산할 수 있다. $s_0 \in P$이면 간선을 하나도 따르지 않는 빈 경로도 허용된다. 예를 들어 첫 번째 예제 공장은 AF, FAFB, AbFFAd, AdydAd를 생산할 수 있다. 이 목록이 전부는 아니다. 각 전이 간선은 제품을 만들 때 무제한으로 사용할 수 있다.

각 스테이션과 영문자의 조합마다 그 문자를 라벨로 가진 나가는 간선은 최대 하나이다. 즉 $(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$)가 주어진다. 각각 스테이션의 수, 포장 스테이션의 수, 전이의 수이다. 스테이션은 1부터 $s$까지 번호가 붙어 있다.

다음 $p$개의 줄에는 포장 스테이션을 나타내는 정수 $i$ ($1 \le i \le s$)가 하나씩 주어진다. 모든 값은 서로 다르다.

다음 $t$개의 줄은 $s_1 \sigma s_2$ 형식이다. 이는 스테이션 $s_1$에서 스테이션 $s_2$로 가고, 간선의 라벨이 문자 $\sigma$임을 뜻한다. $\sigma$는 대문자 또는 소문자 영문자이다. 초기 스테이션은 항상 1번이다. 같은 스테이션에서 같은 문자로 나가는 전이는 두 개 이상 없다.

정수 하나를 출력한다. 구별되지 않는 서로 다른 두 제품의 쌍이 없으면 -1을 출력한다. 있으면 그런 쌍을 이루는 문자열 $a$, $b$에 대해 $|a|+|b|$의 최솟값을 출력한다.

첫 번째 예제 입력의 공장 설계이다. 포장 스테이션은 이중 원으로 표시한다.