トレイルに地図を設置したいと考えている。トレイルは、$1$ から $N$ までの番号が振られた $N$ 個の頂点と $M$ 本の有向辺からなるグラフと考えることができる。自己ループや多重辺は存在しない。

トレイルには始点 $S$ と終点 $E$ がある。利便性を高めるため、$S$ から $E$ へのすべての経路が少なくとも $K$ 個の地図を通るように地図を配置したい。

地図は頂点ごとに $1$ つだけ設置でき（始点や終点を含む）、頂点 $v$ に地図を設置するコストは $C_v$ である。

地図の設置を最小のコストで完了させたい。条件を満たすように地図を設置することが可能かどうかを判定し、可能な場合は、合計コストが最小となるような地図を設置すべき頂点を出力せよ。

入力

入力の最初の行には、頂点数 $N$、辺の数 $M$、地図の最小数 $K$ が与えられる（$2 \le N \le 200$、$1 \le M \le 500$、$1 \le K \le 5$）。

2行目には、始点 $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$ 番目には、2つの整数 $u_j$ と $v_j$ が含まれる。これは $j$ 番目の辺の始点と終点である（$1 \le u_j, v_j \le N$、$u_j \neq v_j$）。

トレイルには自己ループや多重辺が含まれないことが保証されている。

出力

条件を満たすように地図を設置することが不可能な場合は、1行目に $-1$ を出力せよ。

地図の設置が可能な場合は、1行目に合計コストが最小となるような地図を設置する頂点の数 $P$ を出力せよ。2行目には、これらの $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