E. ВыживатеЛи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ли приобрел некоторой еды на обед, но приглашать друзей Ли на обед смертельно опасно. Ли напуган, он не хочет умирать, хотя бы пока не увидит Online IOI 2020...

Всего есть $$$n$$$ различных видов еды и $$$m$$$ лучших друзей Ли. У Ли есть $$$w_i$$$ тарелок $$$i$$$-го вида еды, и у каждого друга Ли есть два любимых вида еды: любимые блюда $$$i$$$-го друга — это $$$x_i$$$ и $$$y_i$$$ ($$$x_i \ne y_i$$$).

Ли начнет вызывать своих друзей по одному. Каждый, кого вызвали, пойдет на кухню и попытается съесть по одной тарелке каждого из его любимых видов еды. Каждый друг зайдет на кухню ровно один раз.

Но проблема в следующем: если друг съест хотя бы одну тарелку еды (суммарно), то он станет абсолютно безвреден. Но если другу нечего есть (не осталось ни $$$x_i$$$, ни $$$y_i$$$), то он съест самого Ли $$$\times\_\times$$$.

Ли может выбрать, в каком порядке приглашать друзей, а потому Ли хочет понять, может ли он пережить ужин или нет. Также его интересует непосредственно сам порядок.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — количество видов еды и количество друзей Ли.

Во второй строке заданы $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \le w_i \le 10^6$$$) — количество тарелок с едой каждого вида.

В $$$i$$$-й строке из следующих $$$m$$$ строк заданы два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — любимые виды еды $$$i$$$-го друга.

Выходные данные

Если Ли может пережить обед, выведите ALIVE (регистр букв не важен), иначе выведите DEAD (регистр не важен).

Также, если он может пережить обед, выведите порядок, в котором Ли следует вызывать друзей. Если существует несколько возможных порядков, выведите любой из них.

Примеры
Входные данные
3 3
1 2 1
1 2
2 3
1 3
Выходные данные
ALIVE
3 2 1
Входные данные
3 2
1 1 0
1 2
1 3
Выходные данные
ALIVE
2 1
Входные данные
4 4
1 2 0 1
1 3
1 2
2 3
2 4
Выходные данные
ALIVE
1 3 2 4
Входные данные
5 5
1 1 1 2 1
3 4
1 2
2 3
4 5
4 5
Выходные данные
ALIVE
5 4 1 3 2
Входные данные
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
Выходные данные
DEAD
Примечание

В первом примере, любой из следующих порядков друзей будет корректным: $$$[1, 3, 2]$$$, $$$[3, 1, 2]$$$, $$$[2, 3, 1]$$$, $$$[3, 2, 1]$$$.

Во втором примере, Ли следует вызвать второго друга первым (тогда он съест тарелку еды $$$1$$$), а потом и первого друга (этот друг съесть тарелку еды $$$2$$$). Если же Ли вызовет сначала первого друга, то он съесть по одной тарелке еды $$$1$$$ и $$$2$$$, а следовательно другому другу ничего не останется.