#P18613. Holiday Regifting
Holiday Regifting
Holiday Regifting
镇上住着 n 个人,第 i 个人的房屋最多能容纳 c_i 件礼物。镇上还有 m 对朋友。每对朋友中,编号较大的人是编号较小的人的“导师”。
最初,所有人的房屋里都没有礼物。每天,圣诞老人派一位精灵给编号为 1 的人送一件礼物。精灵递送礼物时,遵循以下规则:
- 如果接收者放入这件礼物后,房屋仍没有装满,他就收下这件礼物。
- 如果放入这件礼物恰好会装满房屋,他立即把屋内的全部礼物拿出来,使房屋变空,并要求精灵按导师编号从小到大的顺序,给他的每位导师各送一件礼物。剩余礼物全部丢进焚烧炉。
保证每个人的房屋容量,至少等于他的导师数量,所以需要转送的礼物总是够用。
递送途中也可能遇到另一个即将装满房屋的人,从而产生新的递送任务。此时精灵先完成最新产生的任务,再继续此前尚未完成的任务,也就是按调用栈的方式处理。可以证明,每一天的所有递送任务都会在有限步内完成。
圣诞老人担心,某一天结束时,镇上所有房屋都没有礼物,所有礼物都已经被焚烧。请找出第一次出现这种情况的是第几天。若永远不会出现,输出 -1;否则输出这个天数模 998244353 的值。
注意:房屋中的礼物数永远严格小于其容量;正好达到容量时就会立即清空。所求状态是在当天全部递送任务完成之后。
输入格式
第一行两个整数 n、m,分别表示人数和朋友对数。
第二行 n 个整数 c_1,c_2,...,c_n,表示各人的房屋容量。
接下来 m 行,每行两个整数 u_i、v_i,表示一对朋友,满足 u_i<v_i,所以 v_i 是 u_i 的导师。保证所有朋友对互不相同,输入这些朋友对的顺序不作保证。
数据范围:1≤n≤10000,0≤m≤30000,2≤c_i≤100000,1≤u_i<v_i≤n。保证 c_i 不小于编号 i 的人的导师数量。没有连通性保证。
输出格式
若不存在这样的天数,输出 -1;否则输出第一次所有房屋都为空的天数模 998244353 的值。
样例输入 1
5 10
4 3 2 2 2
1 3
3 4
1 4
1 5
2 5
2 4
1 2
2 3
3 5
4 5
样例输出 1
24
样例输入 2
3 0
95 13 77
样例输出 2
95
样例输入 3
12 14
6 7 17 16 20 14 17 16 6 11 6 14
4 11
3 5
2 5
9 11
7 12
1 3
5 9
3 7
3 8
4 9
1 9
4 7
2 11
1 12
样例输出 3
8739360