32947번 - 배달하기

문제

대전과학고등학교의 학생인 건우는 배달 음식을 받아 기숙사의 자신의 호실로 최대한 빨리 가고자 한다.

학교 건물은 1ドル$부터 $N$까지 번호가 붙은 $N$개의 교차점(정점)과, 서로 다른 두 교차점을 연결하는 $M$개의 복도(간선)로 이루어진 양방향 그래프 형태로 구성되어 있다. 이때, 어떤 교차점은 복도와 연결되지 않을 수도 있으며, 특정 교차점들 사이에는 어떠한 방법으로도 서로 도달할 수 없는 경우도 존재할 수 있다.

건우는 출발지인 $S$번 교차점에서 목적지인 $E$번 교차점까지 최대한 빠르게 배달하고 싶지만, 사감 선생님이 학교 내 여러 곳을 CCTV로 감시하며 학생들을 단속하고 있어 경로 선택에 신중을 기해야 한다. 사감 선생님께 배달 음식을 들고 있다가 들키면 벌점을 받기 때문이다.

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

건우는 0ドル$분 시점에 $S$번 교차점에 자리 잡고 있고, 정수 $T$에 대하여 $T$분 시점에 다음 일이 차례로 일어난다.

1. 사감 선생님이 $A_{T \text{ mod } K}$번 교차점을 감시한다. 만약 건우가 이 교차점에 있다면 배달에 실패한다.
2. 만약 건우가 $E$번 교차점에 있다면 배달에 성공한 것이다.
3. 건우가 두 가지 행동 중 하나를 선택한다.
   • 현재 교차점에 머물러 있는다.
   • 현재 교차점과 인접한 교차점이 1ドル$개 이상 있는 경우, 그중 하나를 골라 그 교차점으로 이동한다.
4. 시간이 1ドル$분 흘러간다.

건우가 배달에 성공할 수 있는지, 그리고 만약 가능하다면 배달하는 데에 걸리는 최소 시간을 출력하는 프로그램을 작성하시오.

입력

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

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

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

넷째 줄에는 사감 선생님이 0ドル$분 시점부터 $K-1$분 시점까지 감시하는 교차점의 번호 $A_0, A_1, ..., 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을 출력한다.

제한

노트