Wrocław Zoo

A zoo has $a$ entrance gates (numbered 1 to $a$), $n$ animal enclosures (numbered $a+1$ to $a+n$), and $b$ exit gates (numbered $a+n+1$ to $a+n+b$). Paths connect entrance gates to enclosures, enclosures to other enclosures, and enclosures to exit gates. Every path is bidirectional, and no two paths cross (some run through tunnels or over footbridges, so this is possible).

A class visits the zoo for a nature lesson. The teacher picked $k$ students, each responsible for one animal, and the students strung their talks together into a single story. The tour must visit the enclosures of the chosen animals in the order fixed by that story. The route must satisfy:

• It may start at any entrance gate.
• It must visit the enclosures of all $k$ chosen animals.
• It may end at any exit gate.
• Apart from the start and the end, it may not pass through any gate.
• It must respect the story order: it may not reach the enclosure of the $i$-th chosen animal before it has visited the enclosure of animal $i-1$.
• It must be as short as possible, that is, pass through as few enclosures as possible. An enclosure passed through several times is counted once for each time.

Entering through any gate, visiting the animals' enclosures in story order, and leaving through any exit gate, find the minimum number of enclosures the route passes through. If no such route exists, output $-1$.

The first line contains five integers $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$): the number of entrance gates, enclosures, exit gates, chosen animals, and paths.

Each of the next $k$ lines contains the enclosure number of one chosen animal, given in story order (each animal appears at most once).

Each of the next $m$ lines describes one path as two distinct integers: the numbers of the two gates or enclosures it directly connects.

Print a single line: $-1$ if no route satisfying the rules exists, otherwise the minimum number of enclosures the route must pass through (including the chosen animals' enclosures, counting an enclosure once for each time it is passed through).