Tengo la intención de instalar mapas en el sendero. El sendero puede pensarse como un grafo que consiste en $N$ vértices, numerados del $1$ al $N$, y $M$ aristas dirigidas. No hay bucles ni múltiples aristas dirigidas.

El sendero tiene un punto de inicio $S$ y un destino $E$. Para mayor comodidad, quiero colocar mapas de tal manera que todas las rutas desde $S$ hasta $E$ pasen por al menos $K$ mapas.

Solo se puede instalar un mapa por vértice (incluyendo los puntos de inicio y fin), y el costo de instalar un mapa en el vértice $v$ es $C_v$.

Quiero completar la instalación de mapas al menor costo posible. Determine si los mapas pueden instalarse para cumplir con las condiciones y, si es posible, imprima en qué vértices deben instalarse los mapas para que el costo total sea el mínimo posible.

Entrada

En la primera línea de la entrada, se dan el número de vértices $N$, el número de aristas $M$ y el número mínimo de mapas $K$ ($2 \le N \le 200$, $1 \le M \le 500$, $1 \le K \le 5$).

En la segunda línea, se dan el punto de inicio $S$ y el punto de destino $E$ ($1 \le S, E \le N$, $S \neq E$).

La siguiente línea contiene $N$ enteros $C_1, C_2, \dots, C_N$: los costos de instalar un mapa en los vértices $1, 2, \dots, N$ ($1 \le C_i \le 10^7$).

Las siguientes $M$ líneas describen las aristas. La $j$-ésima de estas líneas contiene dos enteros $u_j$ y $v_j$: el origen y el destino de la $j$-ésima arista ($1 \le u_j, v_j \le N$, $u_j \neq v_j$).

Se garantiza que el sendero no contiene bucles ni múltiples aristas dirigidas.

Salida

Si no es posible instalar mapas para satisfacer las condiciones, se debe imprimir $-1$ en la primera línea.

Si la instalación de mapas es posible, en la primera línea, imprima el número de vértices $P$ en los cuales se debe instalar el mapa para que el costo total sea el mínimo posible. En la segunda línea, imprima las etiquetas de estos $P$ vértices, separados por espacios, en cualquier orden. Si hay varias respuestas posibles, imprima cualquiera de ellas.

Ejemplos

Entrada 1

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

Salida 1

-1

Entrada 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

Salida 2

3
5 6 4