Ли приобрел некоторой еды на обед, но приглашать друзей Ли на обед смертельно опасно. Ли напуган, он не хочет умирать, хотя бы пока не увидит Online IOI 2020...
Всего есть \(n\) различных видов еды и \(m\) лучших друзей Ли. У Ли есть \(w_i\) тарелок \(i\)-го вида еды, и у каждого друга Ли есть два любимых вида еды: любимые блюда \(i\)-го друга — это \(x_i\) и \(y_i\) (\(x_i \ne y_i\)).
Ли начнет вызывать своих друзей по одному. Каждый, кого вызвали, пойдет на кухню и попытается съесть по одной тарелке каждого из его любимых видов еды. Каждый друг зайдет на кухню ровно один раз.
Но проблема в следующем: если друг съест хотя бы одну тарелку еды (суммарно), то он станет абсолютно безвреден. Но если другу нечего есть (не осталось ни \(x_i\), ни \(y_i\)), то он съест самого Ли \(\times\_\times\).
Ли может выбрать, в каком порядке приглашать друзей, а потому Ли хочет понять, может ли он пережить ужин или нет. Также его интересует непосредственно сам порядок.
Выходные данные
Если Ли может пережить обед, выведите ALIVE (регистр букв не важен), иначе выведите DEAD (регистр не важен).
Также, если он может пережить обед, выведите порядок, в котором Ли следует вызывать друзей. Если существует несколько возможных порядков, выведите любой из них.
Примечание
В первом примере, любой из следующих порядков друзей будет корректным: \([1, 3, 2]\), \([3, 1, 2]\), \([2, 3, 1]\), \([3, 2, 1]\).
Во втором примере, Ли следует вызвать второго друга первым (тогда он съест тарелку еды \(1\)), а потом и первого друга (этот друг съесть тарелку еды \(2\)). Если же Ли вызовет сначала первого друга, то он съесть по одной тарелке еды \(1\) и \(2\), а следовательно другому другу ничего не останется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 1
1 2
2 3
1 3
|
ALIVE
3 2 1
|
|
2
|
3 2
1 1 0
1 2
1 3
|
ALIVE
2 1
|
|
3
|
4 4
1 2 0 1
1 3
1 2
2 3
2 4
|
ALIVE
1 3 2 4
|
|
4
|
5 5
1 1 1 2 1
3 4
1 2
2 3
4 5
4 5
|
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
|
DEAD
|