탐방로에 지도를 설치하려고 한다. 탐방로는 $N$개의 정점(1부터 $N$까지 번호가 매겨짐)과 $M$개의 방향성 간선으로 이루어진 그래프로 생각할 수 있다. 자기 자신으로 돌아오는 간선(self-loop)이나 중복된 방향성 간선은 없다.

탐방로에는 시작점 $S$와 도착점 $E$가 있다. 편의를 위해 $S$에서 $E$로 가는 모든 경로가 최소 $K$개의 지도를 거치도록 지도를 설치하고 싶다.

각 정점(시작점과 도착점 포함)에는 최대 하나의 지도만 설치할 수 있으며, 정점 $v$에 지도를 설치하는 비용은 $C_v$이다.

최소 비용으로 지도 설치를 완료하고 싶다. 조건을 만족하도록 지도를 설치할 수 있는지 판단하고, 가능하다면 총비용이 최소가 되도록 지도를 설치해야 할 정점들을 출력하라.

입력

첫 번째 줄에는 정점의 수 $N$, 간선의 수 $M$, 최소 지도 개수 $K$가 주어진다 ($2 \le N \le 200$, $1 \le M \le 500$, $1 \le K \le 5$).

두 번째 줄에는 시작점 $S$와 도착점 $E$가 주어진다 ($1 \le S, E \le N$, $S \neq E$).

세 번째 줄에는 정점 $1, 2, \dots, N$에 지도를 설치하는 비용을 나타내는 $N$개의 정수 $C_1, C_2, \dots, C_N$이 주어진다 ($1 \le C_i \le 10^7$).

다음 $M$개의 줄은 간선을 설명한다. 이 중 $j$번째 줄에는 $j$번째 간선의 시작점과 도착점인 두 정수 $u_j$와 $v_j$가 주어진다 ($1 \le u_j, v_j \le N$, $u_j \neq v_j$).

탐방로에는 자기 자신으로 돌아오는 간선이나 중복된 방향성 간선이 없음이 보장된다.

출력

조건을 만족하도록 지도를 설치할 수 없는 경우, 첫 번째 줄에 -1을 출력한다.

지도 설치가 가능한 경우, 첫 번째 줄에 총비용이 최소가 되도록 지도를 설치해야 할 정점의 개수 $P$를 출력한다. 두 번째 줄에는 이 $P$개의 정점 번호를 공백으로 구분하여 임의의 순서로 출력한다. 가능한 답이 여러 가지라면 그중 아무거나 출력해도 된다.

예제

예제 1

3 2 5
1 3
1 60 35
1 2
2 3

출력 1

-1

예제 2

7 11 1
1 7
100 5 7 16 11 12 100
1 2
1 3
1 4
1 5
2 3
2 6
3 6
4 3
4 7
5 7
6 7

출력 2

3
5 6 4