← 返回题目列表

Codeforces · 1369/E

E. 死李

中文机器翻译题面 查看原题

李买了一些晚餐的食物,但李的朋友却以致命的方式吃晚饭。 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$$$,而第二个朋友就没有食物吃了。