Lee bought some food for dinner time, but Lee's friends eat dinner in a deadly way. Lee is so scared, he doesn't want to die, at least not before seeing Online IOI 2020...

There are $n$ different types of food and $m$ Lee's best friends. Lee has $w_i$ plates of the $i$-th type of food and each friend has two different favorite types of food: the $i$-th friend's favorite types of food are $x_i$ and $y_i$ ($x_i \ne y_i$).

Lee will start calling his friends one by one. Whoever is called will go to the kitchen and will try to eat one plate of each of his favorite food types. Each of the friends will go to the kitchen exactly once.

The only problem is the following: if a friend will eat at least one plate of food (in total) then he will be harmless. But if there is nothing left for him to eat (neither $x_i$ nor $y_i$), he will eat Lee instead $\times\_\times$.

Lee can choose the order of friends to call, so he'd like to determine if he can survive dinner or not. Also, he'd like to know the order itself.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^5$; $1 \le m \le 2 \cdot 10^5$) — the number of different food types and the number of Lee's friends. 

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0 \le w_i \le 10^6$) — the number of plates of each food type.

The $i$-th line of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$) — the favorite types of food of the $i$-th friend. 


-----Output-----

If Lee can survive the dinner then print ALIVE (case insensitive), otherwise print DEAD (case insensitive).

Also, if he can survive the dinner, print the order Lee should call friends. If there are multiple valid orders, print any of them.


-----Examples-----
Input
3 3
1 2 1
1 2
2 3
1 3

Output
ALIVE
3 2 1 

Input
3 2
1 1 0
1 2
1 3

Output
ALIVE
2 1 

Input
4 4
1 2 0 1
1 3
1 2
2 3
2 4

Output
ALIVE
1 3 2 4 

Input
5 5
1 1 1 2 1
3 4
1 2
2 3
4 5
4 5

Output
ALIVE
5 4 1 3 2 

Input
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

Output
DEAD



-----Note-----

In the first example, any of the following orders of friends are correct : $[1, 3, 2]$, $[3, 1, 2]$, $[2, 3, 1]$, $[3, 2, 1]$.

In the second example, Lee should call the second friend first (the friend will eat a plate of food $1$) and then call the first friend (the friend will eat a plate of food $2$). If he calls the first friend sooner than the second one, then the first friend will eat one plate of food $1$ and food $2$ and there will be no food left for the second friend to eat.

Source: codeforces | Difficulty: VERY_HARD
Tags: Graph traversal

Sorting

Implementation

Greedy algorithms

Data structures


Solutions:
import sys
import heapq

class IoTool:
	DEBUG = 0

	def _reader_dbg():
		with open('./input.txt', 'r') as f:
			lines = f.readlines()
		return iter(lines)
	reader = _reader_dbg() if DEBUG else iter(sys.stdin.read().split('\n'))
input = lambda : next(IoTool.reader)

def main():
	(n, m) = map(int, input().split())
	foods = list(map(int, input().split()))
	consume = [0] * n
	food_friend = [[] for _ in range(n)]
	friends_food = []
	for i in range(m):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		friends_food.append([x, y])
		food_friend[x].append(i)
		food_friend[y].append(i)
		consume[x] += 1
		consume[y] += 1
	priority_queue = [(max(0, consume[i] - foods[i]), i) for i in range(n)]
	heapq.heapify(priority_queue)
	mark = [False] * m
	ans = []
	while len(priority_queue) > 0:
		(cost, idx) = heapq.heappop(priority_queue)
		if cost != max(0, consume[idx] - foods[idx]):
			continue
		if cost > 0:
			print('DEAD')
			return
		delta = set()
		for p in food_friend[idx]:
			if not mark[p]:
				(x, y) = friends_food[p]
				consume[x] -= 1
				consume[y] -= 1
				mark[p] = True
				ans.append(p)
				delta.add(x)
				delta.add(y)
		for v in delta:
			heapq.heappush(priority_queue, (max(0, consume[v] - foods[v]), v))
	ans.reverse()
	print('ALIVE')
	print(*map(lambda x: x + 1, ans))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	(n, m) = RL()
	arr = [0] + RLL()
	fris = [RLL() for _ in range(m)]
	rec = [0] * (n + 1)
	recf = [[] for _ in range(n + 1)]
	for (i, (x, y)) in enumerate(fris):
		rec[x] += 1
		rec[y] += 1
		recf[x].append(i)
		recf[y].append(i)
	q = deque()
	visc = [0] * (n + 1)
	for i in range(1, n + 1):
		if rec[i] <= arr[i]:
			q.append(i)
			visc[i] = 1
	vis = [0] * (m + 1)
	res = []
	while q:
		gd = q.popleft()
		for who in recf[gd]:
			if vis[who] == 1:
				continue
			vis[who] = 1
			res.append(who + 1)
			(x, y) = fris[who]
			rec[x] -= 1
			rec[y] -= 1
			if visc[x] == 0 and rec[x] <= arr[x]:
				q.append(x)
				visc[x] = 1
			if visc[y] == 0 and rec[y] <= arr[y]:
				q.append(y)
				visc[y] = 1
	if len(res) == m:
		print('ALIVE')
		print(*res[::-1])
	else:
		print('DEAD')
main()


from collections import defaultdict, deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
w = [int(i) for i in input().split() if i != '\n']
store = [0] * n
graph = defaultdict(list)
for i in range(m):
	(x, y) = map(int, input().split())
	graph[x].append((i + 1, y))
	graph[y].append((i + 1, x))
	w[x - 1] -= 1
	w[y - 1] -= 1
queue = deque()
for i in range(n):
	if w[i] >= 0:
		queue.append(i + 1)
ans = []
visited = [0] * (m + 1)
while queue:
	vertex = queue.popleft()
	for (i, o) in graph[vertex]:
		if visited[i] == 0:
			visited[i] = 1
			ans.append(i)
		w[o - 1] += 1
		if w[o - 1] == 0:
			queue.append(o)
if len(ans) == m:
	sys.stdout.write('ALIVE' + '\n')
	ans.reverse()
	ans = ' '.join(map(str, ans))
	sys.stdout.write(str(ans) + '\n')
else:
	print('DEAD')


def xmax(x, y):
	if x[1] > y[1]:
		return x
	return y

class SegTree:

	def __init__(self, init_val, n, ide_ele, seg_func):
		self.segfunc = seg_func
		self.num = 2 ** (n - 1).bit_length()
		self.ide_ele = ide_ele
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		ll = k
		k += self.num - 1
		self.seg[k] = (ll, self.seg[k][1] + x)
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def update2(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
X = list(map(int, input().split()))
sts = [[] for _ in range(N)]
for i in range(1, M + 1):
	(a, b) = map(int, input().split())
	sts[a - 1].append((i, b - 1))
	sts[b - 1].append((i, a - 1))
	X[a - 1] -= 1
	X[b - 1] -= 1
minf = -10 ** 18 - 1
ss = SegTree([(i, x) for (i, x) in enumerate(X)], N, (-1, minf), xmax)
f = False
R = []
vs = set()
while True:
	(j, mx) = ss.query(0, N)
	if mx < 0:
		f = True
		break
	while sts[j]:
		(i, co) = sts[j].pop()
		if i in vs:
			continue
		vs.add(i)
		ss.update(co, 1)
		R.append(i)
	if len(R) == M:
		break
	ss.update2(j, (j, minf))
if f or len(R) != M:
	print('DEAD')
else:
	print('ALIVE')
	print(*R[::-1])


from sys import stdin, gettrace
from operator import sub
from heapq import heappush, heappop, heapify
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def main():
	(n, m) = map(int, inputi().split())
	ww = [int(a) for a in inputi().split()]
	ff = []
	for _ in range(m):
		(x, y) = map(int, inputi().split())
		ff.append((x - 1, y - 1))
	ffx = [set() for _ in range(n)]
	ss = [0] * n
	for (i, (x, y)) in enumerate(ff):
		ffx[x].add(i)
		ffx[y].add(i)
		ss[x] += 1
		ss[y] += 1
	short = map(sub, ss, ww)
	sh = list(zip(short, range(n)))
	heapify(sh)
	res = []
	used = [False] * n
	while sh:
		(d, i) = heappop(sh)
		if used[i] or d != ss[i] - ww[i]:
			continue
		if d > 0:
			print('DEAD')
			return
		res += ffx[i]
		used[i] = True
		for j in ffx[i]:
			(x, y) = ff[j]
			if y == i:
				y = x
			ffx[y].remove(j)
			if not used[y]:
				ss[y] -= 1
				heappush(sh, (ss[y] - ww[y], y))
	print('ALIVE')
	print(' '.join(map(lambda x: str(x + 1), res[::-1])))
main()


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from collections import deque
	(n, m) = map(int, input().split())
	dish = list(map(int, input().split()))
	used = [0] * m
	friend = [[0, 0] for _ in range(m)]
	fav = [[] for _ in range(n)]
	fav_cnt = [0] * n
	for (i, (x, y)) in enumerate((map(lambda x: int(x) - 1, input().split()) for _ in range(m))):
		friend[i] = [x, y]
		fav[x].append(i)
		fav_cnt[x] += 1
		fav[y].append(i)
		fav_cnt[y] += 1
	dq = deque()
	for i in range(m):
		(x, y) = friend[i]
		if fav_cnt[x] <= dish[x] or fav_cnt[y] <= dish[y]:
			dq.append(i)
			used[i] = 1
	fi = m - 1
	ans = [-1] * m
	while dq:
		i = dq.popleft()
		ans[fi] = i + 1
		fi -= 1
		for d in friend[i]:
			fav_cnt[d] -= 1
			if fav_cnt[d] == dish[d]:
				for j in fav[d]:
					if not used[j]:
						dq.append(j)
						used[j] = 1
	if ans[0] == -1:
		print('DEAD')
	else:
		print('ALIVE')
		print(*ans)
main()


import collections
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
memo = [set() for _ in range(n)]
p = [[] for _ in range(m + 1)]
for i in range(1, m + 1):
	(x, y) = map(int, input().split())
	memo[x - 1].add((i, y - 1))
	memo[y - 1].add((i, x - 1))
	w[x - 1] -= 1
	w[y - 1] -= 1
que = collections.deque()
for i in range(n):
	if w[i] >= 0:
		que.append(i)
res = collections.deque()
exist = [False] * (m + 1)
while que and len(res) < m:
	x = que.popleft()
	for (i, o) in memo[x]:
		if not exist[i]:
			res.append(i)
			exist[i] = True
		w[o] += 1
		if w[o] == 0:
			que.append(o)
if len(res) != m:
	print('DEAD')
else:
	print('ALIVE')
	for i in reversed(res):
		print(i, end=' ')
	print()


(n, m) = list(map(int, input().split()))
w = list(map(int, input().split()))
w2guest = {}
for i in range(n):
	w2guest[i] = set()
guests = []
for i in range(m):
	(a, b) = list(map(int, input().split()))
	guests.append((a - 1, b - 1))
	w2guest[a - 1].add(i)
	w2guest[b - 1].add(i)
ans = []
q = []
visited = set()
in_work = set()
for i in range(n):
	if len(w2guest[i]) == 0:
		visited.add(i)
	elif len(w2guest[i]) <= w[i]:
		q.append(i)
		in_work.add(i)
while len(visited) != n and len(q) > 0:
	a = q.pop()
	gs = w2guest[a]
	ans.extend(gs)
	visited.add(a)
	for g in gs:
		i1 = guests[g][0]
		i2 = guests[g][1]
		if i1 != a:
			w2guest[i1].remove(g)
			if len(w2guest[i1]) == 0:
				visited.add(i1)
			elif len(w2guest[i1]) <= w[i1] and i1 not in in_work:
				in_work.add(i1)
				q.append(i1)
		if i2 != a:
			w2guest[i2].remove(g)
			if len(w2guest[i2]) == 0:
				visited.add(i2)
			elif len(w2guest[i2]) <= w[i2] and i2 not in in_work:
				in_work.add(i2)
				q.append(i2)
if len(visited) != n:
	print('DEAD')
else:
	print('ALIVE')
	print(*reversed([x + 1 for x in ans]))


from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
from heapq import heapify, heappop as pp, heappush as pus
(n, m) = mapi()
a = list(mapi())
b = []
gr = defaultdict(list)
for i in range(m):
	(x, y) = mapi()
	(x, y) = (x - 1, y - 1)
	a[x] -= 1
	a[y] -= 1
	gr[x].append([y, i])
	gr[y].append([x, i])
q = deque()
for i in range(n):
	if a[i] >= 0:
		a[i] = float('inf')
		q.append(i)
vis = {}
res = []
while q:
	node = q.popleft()
	for (w, i) in gr[node]:
		if w not in vis:
			res.append(i)
		if a[w] == float('inf'):
			continue
		a[w] += 1
		if a[w] >= 0:
			q.append(w)
			a[w] = float('inf')
	vis[node] = 1
if len(res) == m:
	print('ALIVE')
	print(*[i + 1 for i in res[::-1]])
else:
	print('DEAD')


import io
import os
from collections import defaultdict
from heapq import heapify, heappop, heappush

def solve(N, M, foodToCount, friendToFood):
	ans = []
	foodToFriends = defaultdict(set)
	for (friend, (x, y)) in enumerate(friendToFood):
		foodToFriends[x].add(friend)
		foodToFriends[y].add(friend)
	heap = [(len(foodToFriends[food]) - foodToCount[food], food) for (food, count) in enumerate(foodToCount)]
	heapify(heap)
	while heap:
		(priority, food) = heappop(heap)
		if len(foodToFriends[food]) - foodToCount[food] != priority:
			continue
		if priority > 0:
			return 'DEAD'
		friends = foodToFriends[food]
		for friend in list(friends):
			assert food in friendToFood[friend]
			(otherFood,) = [x for x in friendToFood[friend] if x != food]
			foodToFriends[food].remove(friend)
			foodToFriends[otherFood].remove(friend)
			ans.append(friend)
			heappush(heap, (len(foodToFriends[otherFood]) - foodToCount[otherFood], otherFood))
		assert not foodToFriends[food]
	assert len(ans) == M
	return 'ALIVE' + '\n' + ' '.join((str(x + 1) for x in ans[::-1]))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M) = [int(x) for x in input().split()]
W = [int(x) for x in input().split()]
XY = [[int(x) - 1 for x in input().split()] for i in range(M)]
ans = solve(N, M, W, XY)
print(ans)


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
W = list(map(int, input().split()))
P = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
G = {}
cnt = [0] * n
for (i, [u, v]) in enumerate(P):
	if u not in G:
		G[u] = []
	if v not in G:
		G[v] = []
	G[u].append(i)
	G[v].append(i)
	cnt[u] += 1
	cnt[v] += 1
S = deque([])
arr = []
used = [0] * m
used2 = [0] * n
for u in range(n):
	if cnt[u] <= W[u]:
		S.append(u)
		used2[u] = 1
while S:
	u = S.popleft()
	if u in G:
		for idx in G[u]:
			if used[idx] == 1:
				continue
			used[idx] = 1
			arr.append(str(idx + 1))
			(x, y) = P[idx]
			cnt[x] -= 1
			cnt[y] -= 1
			if cnt[x] <= W[x] and used2[x] == 0:
				S.append(x)
				used2[x] = 1
			if cnt[y] <= W[y] and used2[y] == 0:
				S.append(y)
				used2[y] = 1
if len(arr) < m:
	print('DEAD')
else:
	print('ALIVE')
	print(' '.join(arr[::-1]))


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
data = [[] for i in range(n)]
fav = []
for i in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (min(x, y), max(x, y))
	w[x - 1] -= 1
	w[y - 1] -= 1
	data[x - 1].append(i)
	data[y - 1].append(i)
	fav.append((x - 1, y - 1))
ans = []
used = [False] * m
useddish = [False] * n
que = deque([])
for i in range(n):
	if w[i] >= 0:
		que.append(i)
		useddish[i] = True
while que:
	id = que.popleft()
	for i in data[id]:
		if not used[i]:
			used[i] = True
			ans.append(i)
			(x, y) = fav[i]
			w[x] += 1
			w[y] += 1
			if w[x] >= 0 and (not useddish[x]):
				que.append(x)
				useddish[x] = True
			if w[y] >= 0 and (not useddish[y]):
				que.append(y)
				useddish[y] = True
if len(ans) == m:
	print('ALIVE')
	ans = [ans[-i - 1] + 1 for i in range(m)]
	print(*ans)
else:
	print('DEAD')


from sys import stdin, stdout

def dead_lee(n, m, w, xy, s):
	queue = []
	for i in range(n):
		if w[i] >= len(s[i]):
			queue.append(i)
	pl = []
	while len(queue) > 0:
		cur = queue.pop()
		w[cur] = 0
		for i in s[cur]:
			pl.append(i + 1)
			if xy[i][0] != cur:
				s[xy[i][0]].remove(i)
				if w[xy[i][0]] == len(s[xy[i][0]]) and w[xy[i][0]] > 0:
					queue.append(xy[i][0])
			else:
				s[xy[i][1]].remove(i)
				if w[xy[i][1]] == len(s[xy[i][1]]) and w[xy[i][1]] > 0:
					queue.append(xy[i][1])
	if len(pl) == m:
		pl.reverse()
		return ['ALIVE', pl]
	else:
		return ['DEAD']
(n, m) = map(int, stdin.readline().split())
w = list(map(int, stdin.readline().split()))
xy = [None for i in range(m)]
s = [set() for i in range(n)]
for i in range(m):
	xy[i] = list(map(int, stdin.readline().split()))
	xy[i][0] -= 1
	xy[i][1] -= 1
	s[xy[i][0]].add(i)
	s[xy[i][1]].add(i)
res = dead_lee(n, m, w, xy, s)
stdout.write(res[0] + '\n')
if len(res) > 1:
	stdout.write(' '.join(map(str, res[1])) + '\n')


import collections
import sys
inpy = [int(x) for x in sys.stdin.read().split()]
(n, m) = inpy[:2]
w = inpy[2:2 + n]
memo = [set() for _ in range(n)]
p = [[] for _i in range(m + 1)]
for i in range(1, m + 1):
	(x, y) = inpy[n + 2 * i:2 + n + 2 * i]
	memo[x - 1].add((i, y - 1))
	memo[y - 1].add((i, x - 1))
	w[x - 1] -= 1
	w[y - 1] -= 1
que = collections.deque()
for i in range(n):
	if w[i] >= 0:
		que.append(i)
res = collections.deque()
exist = [False] * (m + 1)
while que and len(res) < m:
	x = que.popleft()
	for (i, o) in memo[x]:
		if not exist[i]:
			res.append(i)
			exist[i] = True
		w[o] += 1
		if w[o] == 0:
			que.append(o)
if len(res) != m:
	print('DEAD')
else:
	print('ALIVE')
	for i in reversed(res):
		print(i, end=' ')
	print()


(n, m) = map(int, input().split())
fs = [[] for i in range(n + 1)]
(q, vis, req) = [[0] * (n + 1) for i in range(3)]
(res, head, tail) = ([], 0, 0)
used = [0] * (m + 1)
w = [0] + list(map(int, input().split()))
for i in range(1, m + 1):
	(x, y) = map(int, input().split())
	fs[x].append((i, x, y))
	fs[y].append((i, x, y))
	req[x] += 1
	req[y] += 1
for i in range(1, n + 1):
	if req[i] <= w[i]:
		q[tail] = i
		tail += 1
		vis[i] = 1
while head < tail:
	x = q[head]
	head += 1
	for u in fs[x]:
		if not used[u[0]]:
			used[u[0]] = 1
			res.append(u[0])
			if u[1] == x:
				y = u[2]
			else:
				y = u[1]
			req[y] -= 1
			if not vis[y] and req[y] <= w[y]:
				q[tail] = y
				tail += 1
				vis[y] = 1
res.reverse()
if len(res) < m:
	print('DEAD')
else:
	print('ALIVE')
	for u in res:
		print(u)


from collections import defaultdict
(n, m) = list(map(int, input().split()))
W = list(map(int, input().split()))
favorites = []
for i in range(m):
	(x, y) = list(map(int, input().split()))
	favorites.append([x - 1, y - 1])
friends = defaultdict(list)
for (i, (x, y)) in enumerate(favorites):
	friends[x].append(i)
	friends[y].append(i)
S = [len(friends[i]) for i in range(n)]
food_items = set()
for i in range(len(S)):
	if S[i] <= W[i]:
		food_items.add(i)
resolved_food_items = set()
resolved_friends = set()
order = []
while food_items:
	food = food_items.pop()
	resolved_food_items.add(food)
	for friend in friends[food]:
		if friend not in resolved_friends:
			order.append(friend)
			resolved_friends.add(friend)
		for i in favorites[friend]:
			S[i] -= 1
			if i not in resolved_food_items and S[i] <= W[i]:
				food_items.add(i)
if len(order) == m:
	print('ALIVE')
	print(' '.join([str(i + 1) for i in order[::-1]]))
else:
	print('DEAD')


from collections import deque
import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	(n, m) = MI()
	ww = LI()
	xy = LLI1(m)
	fav_mem = [[] for _ in range(n)]
	fav_cnt = [0] * n
	for (j, (x, y)) in enumerate(xy):
		fav_mem[x].append(j)
		fav_mem[y].append(j)
		fav_cnt[x] += 1
		fav_cnt[y] += 1
	q = deque()
	for i in range(n):
		if ww[i] - fav_cnt[i] >= 0:
			q.append(i)
	ans = []
	fini = [False] * n
	finj = [False] * m
	while q:
		i = q.popleft()
		for j in fav_mem[i]:
			if finj[j]:
				continue
			ans.append(j + 1)
			finj[j] = True
			for i0 in xy[j]:
				if fini[i0]:
					continue
				fav_cnt[i0] -= 1
				if ww[i0] - fav_cnt[i0] >= 0:
					q.append(i0)
					fini[i0] = True
	if len(ans) == m:
		print('ALIVE')
		print(*ans[::-1])
	else:
		print('DEAD')
main()


import sys
input = sys.stdin.readline

def line_input():
	return [int(x) for x in input().split()]

def main():
	(n, m) = line_input()
	w = line_input()
	adj = [[] for _ in range(n)]
	edges = []
	deg = [0] * n
	for i in range(m):
		(u, v) = line_input()
		(u, v) = (u - 1, v - 1)
		adj[u].append(v)
		adj[v].append(u)
		edges.append((u, v))
		deg[u] += 1
		deg[v] += 1
	vis = [False] * n
	order = [0] * n
	st = []
	cur = 0
	for i in range(n):
		if deg[i] <= w[i]:
			vis[i] = True
			order[i] = cur
			cur += 1
			st.append(i)
	while len(st):
		u = st.pop()
		for v in adj[u]:
			deg[v] -= 1
			if not vis[v] and deg[v] <= w[v]:
				vis[v] = True
				order[v] = cur
				cur += 1
				st.append(v)
	if sum(vis) < n:
		print('DEAD')
	else:
		print('ALIVE')
		edge_order = [sorted([order[edges[i][0]], order[edges[i][1]]]) for i in range(m)]
		idx = [x for x in range(m)]
		print(*[x + 1 for x in sorted(idx, key=lambda x: edge_order[x], reverse=True)])
main()


import itertools as it
import collections as cc
import heapq as hp
import sys
I = lambda : list(map(int, input().split()))
import operator as op
from functools import reduce
(n, m) = I()
w = I()
de = [0] * n
for i in range(n):
	de[i] = [0]
pre = [0] * m
visi = [0] * m
for i in range(m):
	(x, y) = I()
	x -= 1
	y -= 1
	pre[i] = [x, y]
	de[x][0] += 1
	de[y][0] += 1
	de[x].append(i)
	de[y].append(i)
an = []
te = []
ans = []
for i in range(n):
	if de[i][0] <= w[i]:
		te.append(i)
while len(te) > 0:
	tem = te.pop()
	for i in range(1, len(de[tem])):
		fr = de[tem][i]
		if not visi[fr]:
			visi[fr] = 1
			ans.append(fr + 1)
			fo = pre[fr][0] + pre[fr][1] - tem
			de[fo][0] -= 1
			if de[fo][0] == w[fo]:
				te.append(fo)
if len(ans) == m:
	print('ALIVE')
	print(*ans[::-1])
else:
	print('DEAD')


import sys

def input():
	return sys.stdin.readline().rstrip()

def input_split():
	return [int(i) for i in input().split()]
prefs = []
(n, m) = input_split()
desired = [0 for i in range(n)]
eaters = [[] for i in range(n)]
w = input_split()
for friend in range(m):
	(x, y) = input_split()
	x -= 1
	y -= 1
	prefs.append((x, y))
	desired[x] += 1
	desired[y] += 1
	eaters[x].append(friend)
	eaters[y].append(friend)
isSafe = [False for i in range(n)]
safes = []
for i in range(n):
	if w[i] >= desired[i]:
		safes.append(i)
		isSafe[i] = True
order = []
included = set()
while True:
	new_safes = []
	for dish in safes:
		for friend in eaters[dish]:
			if friend not in included:
				included.add(friend)
				order.append(friend)
			(p1, p2) = prefs[friend]
			if not isSafe[p1] or not isSafe[p2]:
				if not isSafe[p1]:
					desired[p1] -= 1
					if w[p1] >= desired[p1]:
						isSafe[p1] = True
						new_safes.append(p1)
				else:
					desired[p2] -= 1
					if w[p2] >= desired[p2]:
						isSafe[p2] = True
						new_safes.append(p2)
	if len(new_safes) == 0:
		break
	else:
		safes = new_safes
if len(order) == m:
	order.reverse()
	order = [i + 1 for i in order]
	print('ALIVE')
	print(*order, sep=' ')
else:
	print('DEAD')


import os
import sys
from io import BytesIO, IOBase
import threading
from heapq import heapify, heappush, heappop

def main():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	mat = [[] for i in range(n)]
	p = [0] * m
	for i in range(m):
		p[i] = tuple(map(lambda x: int(x) - 1, input().split()))
		mat[p[i][0]].append(i)
		mat[p[i][1]].append(i)
	demand = [0] * n
	done = [False] * n
	ans = []
	q = []
	for i in range(n):
		demand[i] = len(mat[i])
		q.append((demand[i] - arr[i], i))
	heapify(q)
	while len(q):
		(cnt, fd) = heappop(q)
		if done[fd]:
			continue
		elif cnt > 0:
			print('DEAD')
			return
		else:
			ans.extend(mat[fd])
			for fr in mat[fd]:
				for t_f in p[fr]:
					demand[t_f] -= 1
					heappush(q, (demand[t_f] - arr[t_f], t_f))
			done[fd] = True
	res = []
	s = set()
	for i in reversed(ans):
		if i not in s:
			res.append(i + 1)
			s.add(i)
	print('ALIVE')
	print(*res)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
import heapq
import copy
import math
import decimal

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def insr2():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())

def pr_list(a):
	print(*a, sep=' ')

def main():
	tests = 1
	limit = 10 ** 18
	ans = 0
	for test in range(tests):
		[n, m] = inlt()
		w = inlt()
		w = [0] + w
		freq = [0 for i in range(n + 1)]
		s = []
		food_lik = [{} for i in range(n + 1)]
		for i in range(m):
			[x, y] = inlt()
			freq[x] += 1
			freq[y] += 1
			s.append([x, y])
			food_lik[x][i] = 1
			food_lik[y][i] = 1
	h = []
	for i in range(1, n + 1):
		heapq.heappush(h, [-1 * (w[i] - freq[i]), i])
	ans = []
	done = [0 for i in range(m)]
	done_food = [0 for i in range(n + 1)]
	flag = 0
	while h != []:
		curr = heapq.heappop(h)
		if done_food[curr[1]] == 1:
			continue
		done_food[curr[1]] = 1
		if curr[0] > 0:
			flag = 1
			break
		for i in food_lik[curr[1]]:
			if done[i] != 1:
				done[i] = 1
				ans.append(i + 1)
				if s[i][0] == curr[1]:
					freq[s[i][1]] = max(freq[s[i][1]] - 1, 0)
					heapq.heappush(h, [-1 * (w[s[i][1]] - freq[s[i][1]]), s[i][1]])
				else:
					freq[s[i][0]] = max(freq[s[i][0]] - 1, 0)
					heapq.heappush(h, [-1 * (w[s[i][0]] - freq[s[i][0]]), s[i][0]])
		if len(ans) == m:
			break
	if flag == 1:
		print('DEAD')
	else:
		print('ALIVE')
		ans.reverse()
		pr_list(ans)
main()


import sys
import math
import collections
import heapq

def set_debug(debug_mode=False):
	if debug_mode:
		fin = open('input.txt', 'r')
		sys.stdin = fin

def int_input():
	return list(map(int, input().split()))
t = 1
for ti in range(1, t + 1):
	inputarray = [int(x) for x in sys.stdin.read().split()]
	(n, m) = (inputarray[0], inputarray[1])
	(s, w) = ([], [])
	for i in range(2, n + 2):
		w.append(inputarray[i])
	(g, eg, foodm, friendm, x, y) = ([], [], [], [], [], [])
	for i in range(n):
		s.append(0)
		foodm.append(0)
		g.append([])
	for i in range(m):
		friendm.append(0)
		x.append(0)
		y.append(0)
	inppo = n + 2
	for i in range(m):
		(x[i], y[i]) = (inputarray[inppo], inputarray[inppo + 1])
		inppo = inppo + 2
		x[i] = x[i] - 1
		y[i] = y[i] - 1
		u = x[i]
		v = y[i]
		s[u] = s[u] + 1
		s[v] = s[v] + 1
		g[u].append(i)
		g[v].append(i)
		eg.append((v, u))
	myq = []
	ans = []
	for i in range(n):
		heapq.heappush(myq, (-w[i] + s[i], i))
	while len(myq):
		u = myq[0]
		heapq.heappop(myq)
		if u[0] != -w[u[1]] + s[u[1]]:
			continue
		if u[0] > 0:
			print('DEAD')
			sys.exit()
		foodm[u[1]] = 1
		sw = 1
		for i in g[u[1]]:
			if friendm[i] == 0:
				friendm[i] = 1
				if y[i] == u[1]:
					(x[i], y[i]) = (y[i], x[i])
				s[x[i]] = s[x[i]] - 1
				s[y[i]] = s[y[i]] - 1
				heapq.heappush(myq, (-w[y[i]] + s[y[i]], y[i]))
				ans.append(i)
				if len(ans) == m:
					sw = 0
					break
		if sw == 0:
			break
	print('ALIVE')
	for i in ans[::-1]:
		print(i + 1, end=' ')


import sys
from collections import deque

def input():
	return sys.stdin.readline().rstrip()

def input_split():
	return [int(i) for i in input().split()]
(n, m) = input_split()
w = input_split()
num = [0 for i in range(n)]
p = [[] for i in range(n)]
done = [False for i in range(n)]
done_people = [False for i in range(m)]
people = []
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	num[x] += 1
	num[y] += 1
	p[x].append(i)
	p[y].append(i)
	people.append((x, y))
q = deque()
for i in range(n):
	if num[i] <= w[i]:
		q.append(i)
		done[i] = True
ans = []
while len(q) > 0:
	u = q.popleft()
	for elem in p[u]:
		if people[elem][0] == u:
			food = people[elem][1]
		else:
			food = people[elem][0]
		if done_people[elem] == False:
			ans.append(elem)
			done_people[elem] = True
		if done[food] == False:
			num[food] -= 1
			if num[food] <= w[food]:
				q.append(food)
				done[food] = True
for i in done:
	if i == False:
		print('DEAD')
		break
else:
	print('ALIVE')
	ans.reverse()
	ans = [i + 1 for i in ans]
	print(*ans, sep=' ')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
demand = [0] * n
for i in range(n):
	demand[i] = [0]
pref = [0] * m
hasbeen = [0] * m
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	pref[i] = [x, y]
	demand[x][0] += 1
	demand[y][0] += 1
	demand[x].append(i)
	demand[y].append(i)
sol = []
isok = []
for i in range(n):
	if demand[i][0] <= w[i]:
		isok.append(i)
while len(isok) > 0:
	tod = isok.pop()
	for i in range(1, len(demand[tod])):
		friend = demand[tod][i]
		if hasbeen[friend] == 0:
			sol.append(friend + 1)
			hasbeen[friend] = 1
			food = pref[friend][0] + pref[friend][1] - tod
			demand[food][0] -= 1
			if demand[food][0] == w[food]:
				isok.append(food)
if len(sol) == m:
	print('ALIVE')
	sol.reverse()
	print(*sol)
else:
	print('DEAD')


import sys
from collections import deque
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
ds = [0] + list(map(int, input().split()))
pp = [[] for _ in range(n + 1)]
for p in range(1, m + 1):
	(a, b) = map(int, input().split())
	pp[a].append((p, b))
	pp[b].append((p, a))
order = []
pcc = [len(pl) for pl in pp]
(dsvis, moved) = ([0] * (n + 1), [0] * (m + 1))
q = deque([i for i in range(1, n + 1) if pcc[i] <= ds[i]])
for dn in q:
	dsvis[dn] = 1
while q:
	dn = q.popleft()
	for (p, nx) in pp[dn]:
		if moved[p]:
			continue
		order.append(p)
		moved[p] = 1
		pcc[nx] -= 1
		if pcc[nx] <= ds[nx] and (not dsvis[nx]):
			q.append(nx)
			dsvis[nx] = 1
if len(order) == m:
	print('ALIVE')
	print(*list(reversed(order)))
else:
	print('DEAD')


import math
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
w = [int(_) for _ in input().split()]
edges = []
g = [[] for _ in range(n)]
deg = [0] * n
for i in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	g[u].append(v)
	g[v].append(u)
	edges.append((u, v))
	deg[u] += 1
	deg[v] += 1
order = [0] * n
done = [False] * n
stack = []
cur = 0
for i in range(n):
	if deg[i] <= w[i]:
		done[i] = True
		order[i] = cur
		stack.append(i)
		cur += 1
while len(stack) > 0:
	x = stack.pop()
	for i in g[x]:
		deg[i] -= 1
		if not done[i] and deg[i] <= w[i]:
			order[i] = cur
			done[i] = True
			stack.append(i)
			cur += 1
if sum(done) != n:
	print('DEAD')
	exit(0)
sortEdges = []
for i in range(m):
	(u, v) = edges[i]
	if order[u] < order[v]:
		(u, v) = (v, u)
	sortEdges.append((order[u], order[v], i))
print('ALIVE')
print(' '.join(map(lambda i: str(i[2] + 1), sorted(sortEdges, reverse=True))))


import sys
input = sys.stdin.readline
from heapq import *
(n, m) = map(int, input().split())
W = list(map(int, input().split()))
adj = [set() for _ in range(n)]
E = []
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	E.append((x, y))
	adj[x].add(i)
	adj[y].add(i)
VW = [False] * n
Q = []
for i in range(n):
	if len(adj[i]) <= W[i]:
		Q.append(i)
		VW[i] = True
O = []
while Q:
	i = Q.pop()
	for j in adj[i]:
		O.append(j + 1)
		for x in E[j]:
			if i == x:
				continue
			adj[x].remove(j)
			if len(adj[x]) <= W[x] and (not VW[x]):
				VW[x] = True
				Q.append(x)
if len(O) == m:
	print('ALIVE')
	print(*reversed(O))
else:
	print('DEAD')