10428: #2029. 「SHOI2016」巧克力

D 神给他的妹子买了好多好多的巧克力，放在他的储藏室中。作为爱吃巧克力的小 R，当然要去 D 神的储藏室中偷吃巧克力了。

D 神的储藏室中共有 $n$ 个巧克力储藏点，编号从 $0$ 到 $n-1$，每个储藏点中有一块巧克力。共有 $m$ 条单向道路，每条单向路径连接了两个储藏点。小 R 从编号为 $0$ 的储藏点出发，由于他太爱吃巧克力了，他只要经过一个储藏点就一定会吃掉那块巧克力。另外，他不能经过同一个储藏点两次，否则就会触发警报惊动 D 神。

每块巧克力的甜度不同，小 R 吃的第 $i$ 块巧克力可以感受到 $s\cdot k^{i-1}$ 的甜度，其中 $s$ 是该巧克力本身的甜度，$k$ 是给定的不大于 $1$ 的正实数。小 R 感受到的总甜度是他吃每一块巧克力感受到的甜度之和。请给出一条路线使得小 R 感受到的总甜度尽量大。

输入格式

输入文件为 chocolate1.in ~ chocolate10.in。

第一行包含两个正整数 $n,m$ 和一个正实数 $k(0\le k\le 1)$，$n$ 表示巧克力储藏点的数量，$m$ 表示单向道路的数量，$k$ 表示甜度的衰减系数。

第二行 $n$ 个正整数，分别表示每块巧克力的甜度。

接下来 $m$ 行，每行两个正整数 $u,v$，表示有一条从 $u$ 到 $v$ 的单向边。

输出格式

你需要提交输出文件 chocolate1.out ~ chocolate10.out。

第一行一个非负整数 $l$，表示路径长度。
第二行 $l$ 个正整数，依次表示经过每一个储藏点的标号。

样例

样例输入

5 5 0.5
1 3 5 7 2
0 1
0 2
1 3
3 1
2 3
3 4

样例输出

4
0 2 3 1

样例解释

这条路线的总收益为 $1+0.5\times 5+0.25\times 7+0.125\times 3=5.625$。
另一条路线为 $0234$，总收益为 $1+0.5\times 5+0.25\times 7+0.125\times 2=5.5$。

数据范围与提示

评分方式

对于每个测试点，如果你输出的路线出现了以下问题，则该测试点得 $0$ 分：

• 含有非法字符；
• 路线不以编号为 $0$ 的点开始；
• 任意的相邻两个点之间不存在道路；
• 某一个点经过超过一次；
• 经过了不存在的点。

否则，对于每个测试点，假设你的路线能获得的总收益是 $\mathrm{a}\mathrm{n}\mathrm{s}$，我们从小到大给出了 $10$ 个评分参数 $s_1,s_2,\dots ,s_{10}$。如果 ans≥s10\mathrm{ans} \geq s_{10}ans≥s​10​​，你将获得 $10$ 分。否则，如果 si≤ans<si+1s_i \leq \mathrm{ans} < s_{i + 1}s​i​​≤ans<s​i+1​​，你将获得 $i$ 分。