题目描述

一条步道可以看作一张有向图，共有 $N$ 个顶点，编号为 $1$ 到 $N$，以及 $M$ 条有向边。图中没有自环，也没有重边。

步道有一个起点 $S$ 和一个终点 $E$。为了让游客在途中能看到足够多的地图，你希望在若干顶点上安装地图，使得从 $S$ 到 $E$ 的每一条路线都至少经过 $K$ 张地图。

每个顶点最多安装一张地图，包括起点和终点。若在顶点 $v$ 安装地图，需要支付费用 $C_v$。

请判断是否能满足要求。如果可以，请输出一种总费用最小的安装方案。

输入格式

第一行包含三个整数 $N,M,K$，分别表示顶点数、边数和每条 $S$ 到 $E$ 路线至少需要经过的地图数量。

第二行包含两个整数 $S,E$，分别表示起点和终点。

第三行包含 $N$ 个整数 $C_1,C_2,\ldots,C_N$，表示在各顶点安装地图的费用。

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

保证图中没有自环和重边。

输出格式

如果无法安装地图以满足条件，第一行输出：

-1

否则第一行输出一个整数 $P$，表示需要安装地图的顶点数量。

第二行输出 $P$ 个整数，表示安装地图的顶点编号，顺序任意。

输出方案的总费用必须尽可能小。如果有多种最优方案，输出任意一种即可。

数据范围

• $2\le N\le 200$；
• $1\le M\le 500$；
• $1\le K\le 5$；
• $1\le S,E\le N$，且 $S\ne E$；
• $1\le C_i\le 10^7$；
• $1\le u_j,v_j\le N$，且 $u_j\ne v_j$。

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