李买了一些晚餐的食物,但李的朋友却以致命的方式吃晚饭。 Lee很害怕,他不想死,至少在看到Online IOI 2020之前……
有$$$n$$$不同类型的食物和$$$m$$$李最好的朋友。 Lee 有 $$$w_i$$$ 盘第 $$$i$$$ 类型的食物,每个朋友都有两种不同最喜欢的食物类型:第 $$$i$$$ 朋友最喜欢的食物类型是 $$$x_i$$$ 和 $$$y_i$$$ ($$$x_i \ne y_i$$$)。
Lee 将开始一一打电话给他的朋友。被叫到的人都会去厨房,尝试吃一盘他最喜欢的食物。每个朋友都会去厨房一次。
唯一的问题是:如果一个朋友(总共)至少吃一盘食物,那么他将是无害的。但如果他没有东西可吃($$$x_i$$$ 和 $$$y_i$$$ 都没有),他就会吃 Lee $$$\times\_\times$$$。
Lee 可以选择给朋友打电话的顺序,因此他想确定自己是否能熬过晚餐。另外,他想知道命令本身。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — 不同食物类型的数量和 Lee 朋友的数量。
第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \le w_i \le 10^6$$$) — 每种食物类型的盘子数量。
接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — 第 $$$i$$$ 位朋友最喜欢的食物类型。
输出
如果 Lee 能在晚餐中幸存下来,则打印 ALIVE(不区分大小写),否则打印 DEAD(不区分大小写)。
另外,如果他能在晚餐中幸存下来,请打印李应该给朋友打电话的命令。如果有多个有效订单,则打印其中任何一个。
示例
输入 #1
3 3 1 2 1 1 2 2 3 1 3
输出 #1
ALIVE 3 2 1
输入 #2
3 2 1 1 0 1 2 1 3
输出 #2
ALIVE 2 1
输入 #3
4 4 1 2 0 1 1 3 1 2 2 3 2 4
输出 #3
ALIVE 1 3 2 4
输入#4
5 5 1 1 1 2 1 3 4 1 2 2 3 4 5 4 5
输出#4
ALIVE 5 4 1 3 2
输入 #5
4 10 2 4 1 4 3 2 4 2 4 1 3 1 4 1 1 3 3 2 2 1 3 1 2 4
输出 #5
DEAD
注意
在第一个示例中,以下任意好友顺序都是正确的:$$$[1, 3, 2]$$$、$$$[3, 1, 2]$$$、$$$[2, 3, 1]$$$、$$$[3, 2, 1]$$$。
在第二个例子中,Lee应该先打电话给第二个朋友(这个朋友会吃一盘食物$$$1$$$),然后打电话给第一个朋友(这个朋友会吃一盘食物$$$2$$$)。如果他比第二个朋友早给第一个朋友打电话,那么第一个朋友会吃掉一盘食物 $$$1$$$ 和食物 $$$2$$$,而第二个朋友就没有食物吃了。