Je souhaite installer des cartes sur le sentier. Le sentier peut être représenté comme un graphe composé de $N$ sommets, numérotés de $1$ à $N$, et de $M$ arêtes orientées. Il n'y a pas de boucles ni d'arêtes multiples.

Le sentier possède un point de départ $S$ et une destination $E$. Pour plus de commodité, je souhaite placer des cartes de telle sorte que tous les chemins allant de $S$ à $E$ passent par au moins $K$ cartes.

Une seule carte peut être installée par sommet (y compris les points de départ et d'arrivée), et le coût d'installation d'une carte au sommet $v$ est $C_v$.

Je souhaite terminer l'installation des cartes au coût le plus bas possible. Déterminez si les cartes peuvent être installées pour satisfaire ces conditions et, si c'est possible, indiquez les sommets où les cartes doivent être installées afin que le coût total soit minimal.

Entrée

La première ligne de l'entrée contient le nombre de sommets $N$, le nombre d'arêtes $M$ et le nombre minimum de cartes $K$ ($2 \le N \le 200$, $1 \le M \le 500$, $1 \le K \le 5$).

La deuxième ligne contient le point de départ $S$ et le point d'arrivée $E$ ($1 \le S, E \le N$, $S \neq E$).

La ligne suivante contient $N$ entiers $C_1, C_2, \dots, C_N$ : les coûts d'installation d'une carte aux sommets $1, 2, \dots, N$ ($1 \le C_i \le 10^7$).

Les $M$ lignes suivantes décrivent les arêtes. La $j$-ième de ces lignes contient deux entiers $u_j$ et $v_j$ : la source et la destination de la $j$-ième arête ($1 \le u_j, v_j \le N$, $u_j \neq v_j$).

Il est garanti que le sentier ne contient ni boucles ni arêtes multiples.

Sortie

S'il n'est pas possible d'installer des cartes pour satisfaire les conditions, imprimez $-1$ sur la première ligne.

Si l'installation des cartes est possible, imprimez sur la première ligne le nombre de sommets $P$ où la carte doit être installée pour que le coût total soit minimal. Sur la deuxième ligne, imprimez les étiquettes de ces $P$ sommets, séparées par des espaces, dans n'importe quel ordre. S'il existe plusieurs réponses possibles, imprimez-en n'importe laquelle.

Exemples

Entrée 1

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

Sortie 1

-1

Entrée 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

Sortie 2

3
5 6 4