Я планирую установить карты на маршруте. Маршрут можно представить как граф, состоящий из $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

Пример 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

3
5 6 4