Tôi dự định lắp đặt các bản đồ trên đường mòn. Đường mòn có thể được coi là một đồ thị gồm $N$ đỉnh, được đánh số từ $1$ đến $N$, và $M$ cạnh có hướng. Đồ thị không có khuyên và không có đa cạnh.

Đường mòn có một điểm bắt đầu $S$ và một điểm kết thúc $E$. Để thuận tiện hơn, tôi muốn đặt các bản đồ sao cho tất cả các lộ trình từ $S$ đến $E$ đều đi qua ít nhất $K$ bản đồ.

Mỗi đỉnh chỉ có thể lắp đặt tối đa một bản đồ (bao gồm cả điểm bắt đầu và điểm kết thúc), và chi phí để lắp đặt một bản đồ tại đỉnh $v$ là $C_v$.

Tôi muốn hoàn thành việc lắp đặt bản đồ với chi phí thấp nhất có thể. Hãy xác định xem liệu có thể lắp đặt các bản đồ để thỏa mãn các điều kiện hay không, và nếu có thể, hãy in ra những đỉnh nào cần lắp đặt bản đồ để tổng chi phí là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số đỉnh $N$, số cạnh $M$ và số lượng bản đồ tối thiểu $K$ ($2 \le N \le 200$, $1 \le M \le 500$, $1 \le K \le 5$).

Dòng thứ hai chứa điểm bắt đầu $S$ và điểm kết thúc $E$ ($1 \le S, E \le N, S \neq E$).

Dòng tiếp theo chứa $N$ số nguyên $C_1, C_2, \dots, C_N$: chi phí lắp đặt bản đồ tại các đỉnh $1, 2, \dots, N$ ($1 \le C_i \le 10^7$).

$M$ dòng tiếp theo mô tả các cạnh. Dòng thứ $j$ trong số này chứa hai số nguyên $u_j$ và $v_j$: đỉnh đầu và đỉnh cuối của cạnh thứ $j$ ($1 \le u_j, v_j \le N, u_j \neq v_j$).

Đảm bảo rằng đường mòn không chứa khuyên và không có đa cạnh.

Dữ liệu ra

Nếu không thể lắp đặt bản đồ để thỏa mãn các điều kiện, hãy in $-1$ trên dòng đầu tiên.

Nếu việc lắp đặt bản đồ là khả thi, trên dòng đầu tiên, hãy in số lượng đỉnh $P$ cần lắp đặt bản đồ để tổng chi phí là nhỏ nhất. Trên dòng thứ hai, in nhãn của $P$ đỉnh này, cách nhau bởi dấu cách, theo bất kỳ thứ tự nào. Nếu có nhiều phương án trả lời, hãy in bất kỳ phương án nào trong số đó.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

-1

Dữ liệu vào 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

Dữ liệu ra 2

3
5 6 4