题目描述

一条遛狗步道可以看作一张由 $N$ 个顶点和 $M$ 条有向边组成的图。图中给定两个不同的顶点：起点 $S$ 和终点 $E$。

你可以在一些顶点上安装地图。顶点 $v$ 上最多安装一张地图，安装费用为正整数 $C_v$。起点和终点也允许安装地图。

你需要选择若干顶点安装地图，使得从 $S$ 到 $E$ 的每一条路径都至少经过 $K$ 个安装了地图的顶点。

若图中根本不存在从 $S$ 到 $E$ 的路径，则不安装任何地图也视为满足要求。

请判断是否存在可行方案。若存在，输出总费用最小的一组安装位置。

输入格式

第一行包含三个整数 $N,M,K$。

$$2\le N\le 200, \qquad 1\le M\le 500, \qquad 1\le K\le 5.$$

第二行包含两个整数 $S,E$。

$$1\le S,E\le N, \qquad S\ne E.$$

第三行包含 $N$ 个正整数

$$C_1,C_2,\ldots,C_N,$$

其中

$$1\le C_i\le 10^7.$$

接下来 $M$ 行，每行包含两个整数 $u_j,v_j$，表示存在一条从 $u_j$ 指向 $v_j$ 的有向边。

图中不存在自环。对于同一个有序点对 $(u,v)$，至多出现一条从 $u$ 到 $v$ 的边；但 $u\to v$ 和 $v\to u$ 可以同时存在。

图中不保证存在从 $S$ 到 $E$ 的路径。

输出格式

若不存在满足要求的安装方案，输出一行：

-1

否则：

• 第一行输出安装地图的顶点数 $P$；
• 第二行输出这 $P$ 个顶点的编号，顺序任意。

要求输出的集合费用最小。

$$0\le P\le N.$$

当 $P=0$ 时，第二行可以为空。

样例 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 4 6