배달하기

건우는 배달 음식을 받아 기숙사에 있는 자신의 호실로 최대한 빨리 가려고 한다.

학교 건물은 $1$부터 $N$까지 번호가 붙은 $N$개의 교차점(정점)과, 서로 다른 두 교차점을 잇는 $M$개의 복도(간선)로 이루어진 양방향 그래프이다. 복도와 연결되지 않은 교차점이 있을 수 있고, 어떤 두 교차점 사이에는 어떤 경로로도 도달할 수 없는 경우도 있을 수 있다.

건우는 출발지인 $S$번 교차점에서 목적지인 $E$번 교차점까지 최대한 빨리 가고 싶다. 하지만 사감 선생님이 학교 곳곳을 CCTV로 감시하고 있어 경로를 신중하게 골라야 한다. 사감 선생님에게 배달 음식을 들고 있는 모습을 들키면 벌점을 받는다.

사감 선생님의 CCTV 감시는 $K$분을 주기로 반복된다. 건우가 출발한 지 $T$분이 지나면 사감 선생님은 $A_{T \bmod K}$번 교차점을 감시한다. 여기서 $T \bmod K$는 $T$를 $K$로 나눈 나머지이다.

건우는 $0$분에 $S$번 교차점에 있다. 정수 $T$에 대하여 $T$분 시점에 다음 일이 순서대로 일어난다.

1. 사감 선생님이 $A_{T \bmod K}$번 교차점을 감시한다. 이때 건우가 그 교차점에 있으면 배달에 실패한다.
2. 건우가 $E$번 교차점에 있으면 배달에 성공한다.
3. 건우는 두 가지 행동 중 하나를 고른다. 현재 교차점에 머무르거나, 인접한 교차점이 하나 이상 있을 때 그중 하나로 이동한다.
4. 1분이 지난다.

건우가 배달에 성공할 수 있는지 판단하고, 성공할 수 있다면 배달하는 데 걸리는 최소 시간을 구하시오.

첫째 줄에 교차점의 개수 $N$과 복도의 개수 $M$이 공백으로 구분되어 주어진다. ($2 \leq N \leq 300000$, $1 \leq M \leq \min\left(300000, \frac{N(N-1)}{2}\right)$)

둘째 줄에 건우의 출발지 교차점 번호 $S$와 목적지 교차점 번호 $E$가 공백으로 구분되어 주어진다. ($1 \leq S, E \leq N$, $S \neq E$)

셋째 줄에 사감 선생님이 감시를 반복하는 주기 $K$가 주어진다. ($1 \leq K \leq 300000$)

넷째 줄에 사감 선생님이 $0$분부터 $K-1$분까지 감시하는 교차점 번호 $A_0, A_1, \ldots, A_{K-1}$이 공백으로 구분되어 주어진다. 사감 선생님은 이 순서대로 CCTV 감시를 반복하며, $0$분에 $S$번 교차점은 감시하지 않는다. ($1 \leq A_i \leq N$, $A_0 \neq S$)

다음 $M$개의 줄에는 교차점 번호 $u$, $v$가 공백으로 구분되어 주어진다. 이는 $u$번 교차점과 $v$번 교차점 사이에 양방향 복도가 있다는 뜻이다. 임의의 두 교차점을 잇는 복도는 최대 $1$개이다. ($1 \leq u < v \leq N$)

입력으로 주어지는 모든 수는 정수이다.

건우가 배달에 성공할 수 있다면 배달하는 데 걸리는 최소 시간을 분 단위의 정수로 출력한다. 배달에 성공할 수 없다면 $-1$을 출력한다.