Source : NOI2016贵州省选
Description
D 神给他的妹子买了好多好多的巧克力,放在他的储藏室中。作为爱吃巧克力的小 R,当然要去 D 神的储藏室中偷吃巧克力了。
D 神的储藏室中共有n个巧克力储藏点,编号从 0 到n-1,每个储藏点中有一块巧克力。共有m条单向道路,每条单向路径连接了两个储藏点。小R从编号为 0 的储藏点出发,由于他太爱吃巧克力了,他只要经过一个储藏点就一定会吃掉那块巧克力。另外,他不能经过同一个储藏点两次,否则就会触发警报惊动 D 神。
每块巧克力的甜度不同,小R吃的第i块巧克力可以感受到ski-1的甜度,其中s是该巧克力本身的甜度,k是给定的不大于 1 的正实数。小 R 感受到的总甜度是他吃每一块巧克力感受到的甜度之和。请给出一条路线使得小 R 感受到的总甜度尽量大。
Input
第一行包含两个正整数n,m和一个正实数k(0<k≤1),n表示巧克力储藏点的数量,m表示单向道路的数量,k表示甜度的衰减系数。
第二行n个正整数,分别表示每块巧克力的甜度。
接下来m行,每行两个正整数u,v,表示有一条从u到v的一条单向边。
Output
第一行一个非负整数L,表示路径长度。
第二行L个正整数,分别表示经过每一个储藏点的标号。
Sample Input
5 5 0.5
1 3 5 7 2
0 1
0 2
1 3
3 1
2 3
3 4
Sample Output
4
0 2 3 1
Hint