브로츠와프 동물원

어느 동물원에는 입구 게이트 $a$ 개(번호 1번부터 $a$번까지), 동물 우리 $n$ 개(번호 $a+1$번부터 $a+n$번까지), 출구 게이트 $b$ 개(번호 $a+n+1$번부터 $a+n+b$번까지)가 있습니다. 동물원의 길은 입구 게이트와 우리 사이, 우리와 우리 사이, 우리와 출구 게이트 사이를 잇습니다. 모든 길은 양방향이며 서로 교차하지 않습니다(터널이나 구름다리로 이어지기도 하므로 가능합니다).

한 학급이 자연 관찰 수업을 하러 동물원에 갑니다. 선생님은 학생 $k$ 명에게 각자 동물 한 마리씩을 맡겨 발표를 준비하게 했고, 학생들은 그 발표를 하나의 이야기로 이어 붙였습니다. 관람 경로는 그 이야기가 정한 순서대로 지정된 동물들의 우리를 방문해야 합니다. 경로는 다음 조건을 만족해야 합니다.

• 아무 입구 게이트에서나 출발할 수 있습니다.
• 지정된 $k$ 마리 동물의 우리를 모두 방문해야 합니다.
• 아무 출구 게이트에서나 끝낼 수 있습니다.
• 출발점과 도착점을 제외하고는 중간에 어떤 게이트도 지나갈 수 없습니다.
• 이야기 순서를 지켜야 합니다. 즉, $i-1$번째 동물의 우리를 방문하기 전에는 $i$번째 동물의 우리에 도달할 수 없습니다.
• 가능한 한 짧아야 합니다. 즉, 지나가는 우리의 수가 최소가 되어야 합니다. 같은 우리를 여러 번 지나가면 지나간 횟수만큼 셉니다.

아무 입구로 들어가 이야기 순서대로 동물 우리를 방문한 뒤 아무 출구로 나올 때, 지나가야 하는 우리 수의 최솟값을 구하세요. 그러한 경로가 존재하지 않으면 $-1$을 출력합니다.

첫 번째 줄에 정수 $a$, $n$, $b$, $k$, $m$ 다섯 개가 공백으로 구분되어 주어집니다($1 \le a \le 25$, $1 \le b \le 25$, $1 \le k \le 100$, $1 \le n \le 1000$, $1 \le m \le 5000$). 각각 입구 게이트 수, 우리 수, 출구 게이트 수, 지정된 동물 수, 길의 수를 뜻합니다.

이어지는 $k$개의 줄에는 지정된 동물이 있는 우리의 번호가 이야기 순서대로 한 줄에 하나씩 주어집니다(각 동물은 최대 한 번만 등장합니다).

이어지는 $m$개의 줄에는 길의 정보가 한 줄에 하나씩 주어집니다. 각 길은 서로 다른 두 정수로 이루어지며, 그 길이 직접 잇는 두 게이트 또는 우리의 번호입니다.

한 줄을 출력합니다. 규칙을 만족하는 경로가 없으면 $-1$을, 그렇지 않으면 경로가 반드시 지나가야 하는 우리 수의 최솟값을 출력합니다(지정된 동물의 우리를 포함하며, 같은 우리를 지나갈 때마다 각각 셉니다).