Zamierzam zainstalować mapy na szlaku. Szlak można przedstawić jako graf składający się z $N$ wierzchołków, ponumerowanych od $1$ do $N$, oraz $M$ skierowanych krawędzi. W grafie nie ma pętli własnych ani wielokrotnych krawędzi skierowanych.

Szlak ma punkt startowy $S$ oraz punkt docelowy $E$. Dla większej wygody chcę rozmieścić mapy w taki sposób, aby każda trasa z $S$ do $E$ przechodziła przez co najmniej $K$ map.

W każdym wierzchołku można zainstalować tylko jedną mapę (wliczając w to punkty startowy i końcowy), a koszt instalacji mapy w wierzchołku $v$ wynosi $C_v$.

Chcę dokonać instalacji map przy najniższym możliwym koszcie. Określ, czy możliwe jest zainstalowanie map zgodnie z warunkami, a jeśli tak, wypisz wierzchołki, w których należy zainstalować mapy, tak aby całkowity koszt był minimalny.

Wejście

W pierwszej linii wejścia podano liczbę wierzchołków $N$, liczbę krawędzi $M$ oraz minimalną liczbę map $K$ ($2 \le N \le 200$, $1 \le M \le 500$, $1 \le K \le 5$).

W drugiej linii podano punkt startowy $S$ oraz punkt docelowy $E$ ($1 \le S, E \le N$, $S \neq E$).

Kolejna linia zawiera $N$ liczb całkowitych $C_1, C_2, \dots, C_N$: koszty instalacji mapy w wierzchołkach $1, 2, \dots, N$ ($1 \le C_i \le 10^7$).

Następne $M$ linii opisuje krawędzie. $j$-ta z tych linii zawiera dwie liczby całkowite $u_j$ oraz $v_j$: wierzchołek początkowy i końcowy $j$-tej krawędzi ($1 \le u_j, v_j \le N$, $u_j \neq v_j$).

Gwarantuje się, że szlak nie zawiera pętli własnych ani wielokrotnych krawędzi skierowanych.

Wyjście

Jeśli zainstalowanie map spełniających warunki nie jest możliwe, w pierwszej linii należy wypisać $-1$.

Jeśli instalacja map jest możliwa, w pierwszej linii wypisz liczbę wierzchołków $P$, w których należy zainstalować mapy, aby całkowity koszt był minimalny. W drugiej linii wypisz numery tych $P$ wierzchołków, oddzielone spacjami, w dowolnej kolejności. Jeśli istnieje kilka możliwych rozwiązań, wypisz dowolne z nich.

Przykład

Wejście 1

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

Wyjście 1

-1

Wejście 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

Wyjście 2

3
5 6 4