任务安排
题号:NC236175
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

playf有n个任务,其中有些任务需要完成它所有的前置任务才能开始。从0时刻开始,第i个任务从开始到完成需要消耗t_i的时间,可以多个任务同时进行。playf想要尽可能早地完成这n个任务,但是他很懒,他想知道在完成这n个任务所用时间最短的前提下,有哪些任务是有可能可以拖延的。
拖延的意思是,对于一个任务i,如果存在某一时刻t,可以开始任务i,但是playf可以不需要在t时刻马上开始,他最终也可以让完成这n个任务所用的时间最短。你能帮帮他吗。

输入描述:

第一行输入两个整数,分别表示任务个数和任务之间的关系数。
接下来一行,输入n个整数,分别表示完成每个任务需要的时间。
接下来m行,每行输入两个整数,表示u_iv_i的一个前置任务。

输出描述:

如果playf能完成这n个任务,则输出两行。第一行输出一个整数S,表示他可能可以拖延的任务的个数,第二行从小到大输出S个整数,以空格分离,表示哪些任务是可能可以拖延的。否则,如果playf不能完成这n个任务,输出一行-1
示例1

输入

复制
6 8
3 3 10 1 6 2
1 4
1 2
1 3
6 2
3 2
4 6
4 5
2 5

输出

复制
2
4 6

说明

n个任务最短的完成时间是22。

t=3时,可以完成任务1,此时不必立即开始任务4,只需要在t<=10的某一个时刻开始任务4,最终还是能在t=22时完成n个任务。

同样,如果在t=4时完成任务4,也不必立即开始任务6,最终还是能以最短时间完成所有任务。

示例2

输入

复制
5 6
1 2 3 4 5
1 2
1 3
2 3
3 4
4 1
5 2

输出

复制
-1

说明

任务1,2,3,4互相依赖,无法开始任何一个任务,因此无法完成。