我打算在路徑上安裝地圖。這條路徑可以被視為一個由 $N$ 個頂點（編號從 $1$ 到 $N$）和 $M$ 條有向邊組成的圖。圖中沒有自環，也沒有多重邊。

這條路徑有一個起點 $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$)。

第三行包含 $N$ 個整數 $C_1, C_2, \dots, C_N$：分別為在頂點 $1, 2, \dots, N$ 安裝地圖的成本 ($1 \le C_i \le 10^7$)。

接下來 $M$ 行描述邊。第 $j$ 行包含兩個整數 $u_j$ 和 $v_j$：第 $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