Given n boxes, each box is given in the format [status, candies, keys, containedBoxes] where:

status[i]: an integer which is 1 if box[i] is open and 0 if box[i] is closed.
candies[i]: an integer representing the number of candies in box[i].
keys[i]: an array contains the indices of the boxes you can open with the key in box[i].
containedBoxes[i]: an array contains the indices of the boxes found in box[i].

You will start with some boxes given in initialBoxes array. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.
Return the maximum number of candies you can get following the rules above.
 
Example 1:
Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2. Box 1 is closed and you don't have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.

Example 2:
Input: status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
Output: 6
Explanation: You have initially box 0. Opening it you can find boxes 1,2,3,4 and 5 and their keys. The total number of candies will be 6.

Example 3:
Input: status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1]
Output: 1

Example 4:
Input: status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = []
Output: 0

Example 5:
Input: status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]
Output: 7

 
Constraints:

1 <= status.length <= 1000
status.length == candies.length == keys.length == containedBoxes.length == n
status[i] is 0 or 1.
1 <= candies[i] <= 1000
0 <= keys[i].length <= status.length
0 <= keys[i][j] < status.length
All values in keys[i] are unique.
0 <= containedBoxes[i].length <= status.length
0 <= containedBoxes[i][j] < status.length
All values in containedBoxes[i] are unique.
Each box is contained in one box at most.
0 <= initialBoxes.length <= status.length
0 <= initialBoxes[i] < status.length

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Graph algorithms

Graph traversal

Starter code: class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        

Solutions:
class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		reachable = [False] * len(status)
		visited = [False] * len(status)
		for box in initialBoxes:
			reachable[box] = True
		for i in range(len(containedBoxes)):
			for inside in containedBoxes[i]:
				reachable[inside] = False
		queue = initialBoxes
		target = []
		ret = 0
		while queue:
			for box in queue:
				if status[box] == 1 and reachable[box] and (not visited[box]):
					ret += candies[box]
					visited[box] = True
					for key in keys[box]:
						if status[key] == 0:
							status[key] = 1
							if reachable[key]:
								target.append(key)
					for inside in containedBoxes[box]:
						reachable[inside] = True
						if status[inside] == 1:
							target.append(inside)
				else:
					target.append(box)
			if target == queue:
				break
			queue = target
			target = []
		return ret


from collections import deque

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		q = deque(initialBoxes)
		visited = set()
		res = 0
		while q:
			(itr, opened) = (len(q), False)
			opened = False
			while itr:
				itr -= 1
				v = q.popleft()
				if status[v]:
					opened = True
					res += candies[v]
					visited.add(v)
					for x in keys[v]:
						status[x] = 1
					for x in containedBoxes[v]:
						if x not in visited:
							q.append(x)
				elif v not in visited:
					q.append(v)
			if not opened:
				return res
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		reachable = [False for _ in status]
		for i in initialBoxes:
			reachable[i] = True
		can_open = [val == 1 for val in status]
		nodes_to_visit = [b for b in range(len(status)) if reachable[b] and can_open[b]]
		total_candies = 0
		while len(nodes_to_visit) >= 1:
			curr_node = nodes_to_visit[0]
			nodes_to_visit = nodes_to_visit[1:]
			total_candies += candies[curr_node]
			for k in keys[curr_node]:
				if not can_open[k] and reachable[k]:
					nodes_to_visit.append(k)
				can_open[k] = True
			for b in containedBoxes[curr_node]:
				if not reachable[b] and can_open[b]:
					nodes_to_visit.append(b)
				reachable[b] = True
		return total_candies


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		stack = deque(initialBoxes)
		seen = set()
		kseen = set()
		while stack:
			for _ in range(len(stack)):
				box = stack.popleft()
				seen.add(box)
				for key in keys[box]:
					status[key] = 1
				for tbox in containedBoxes[box]:
					if tbox not in seen:
						stack.append(tbox)
		res = 0
		for box in seen:
			if candies[box] and status[box]:
				res += candies[box]
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		n = len(status)
		visited = [0] * n
		unopened = [0] * n
		opened = []
		ans = 0
		for b in initialBoxes:
			if status[b] == 1:
				opened.append(b)
				visited[b] = 1
			else:
				unopened[b] = 1
		while opened:
			q2 = []
			for b in opened:
				ans += candies[b]
				for bb in containedBoxes[b]:
					if visited[bb] == 0:
						if status[bb] == 1:
							q2.append(bb)
						else:
							unopened[bb] = 1
				for k in keys[b]:
					status[k] = 1
					if unopened[k] == 1 and visited[k] == 0:
						unopened[k] = 0
						visited[k] = 1
						q2.append(k)
			opened = q2
		return ans


from typing import List
import collections

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		parent = {}
		used = {}
		ans = 0
		for i in range(len(containedBoxes)):
			used[i] = False
			for box in containedBoxes[i]:
				parent[box] = i
		queue = collections.deque(initialBoxes)
		for box in initialBoxes:
			used[box] = True
		while queue:
			curr_box = queue.popleft()
			ans += candies[curr_box]
			for key in keys[curr_box]:
				status[key] = 1
				if key in parent and used[parent[key]] and (not used[key]):
					used[key] = True
					queue.append(key)
			for box in containedBoxes[curr_box]:
				if status[box] and (not used[box]):
					used[box] = True
					queue.append(box)
		return ans


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		total = 0
		boxes = initialBoxes[:]
		locked = []
		while boxes:
			if not any([status[temp] for temp in boxes]):
				break
			box = boxes.pop(0)
			if status[box]:
				total += candies[box]
				for contained in containedBoxes[box]:
					boxes.append(contained)
				for key in keys[box]:
					status[key] = 1
			else:
				boxes.append(box)
		return total


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		candy_count = 0
		my_boxes = initialBoxes
		my_keys = []
		while my_boxes:
			l = len(my_boxes)
			opened_new = False
			for b_i in range(l - 1, -1, -1):
				my_box = my_boxes[b_i]
				if status[my_box] or my_box in my_keys:
					my_boxes.pop(b_i)
					my_boxes.extend(containedBoxes[my_box])
					candy_count += candies[my_box]
					my_keys.extend(keys[my_box])
					opened_new = True
			if not opened_new:
				return candy_count
		return candy_count


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		active_set = initialBoxes
		total_candies = 0
		changed = True
		while changed:
			changed = False
			next_active_set = []
			for b in active_set:
				if status[b]:
					changed = True
					total_candies += candies[b]
					for k in keys[b]:
						status[k] = 1
					next_active_set += containedBoxes[b]
				else:
					next_active_set.append(b)
			active_set = next_active_set
		return total_candies

	def SLOWmaxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		open_boxes = set()
		closed_boxes = set()
		for b in initialBoxes:
			if status[b]:
				open_boxes.add(b)
			else:
				closed_boxes.add(b)
		total_candies = 0
		while len(open_boxes) > 0:
			b = open_boxes.pop()
			total_candies += candies[b]
			for key in keys[b]:
				status[key] = 1
				if key in closed_boxes:
					closed_boxes.remove(key)
					open_boxes.add(key)
			for bb in containedBoxes[b]:
				if status[bb]:
					open_boxes.add(bb)
				else:
					closed_boxes.add(bb)
		return total_candies


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		(q, res) = (collections.deque(initialBoxes), 0)
		while q:
			l = len(q)
			for _ in range(l):
				(b, changed) = (q.popleft(), False)
				if status[b]:
					changed = True
					res += candies[b]
					q.extend(containedBoxes[b])
					for i in keys[b]:
						status[i] = 1
				else:
					q.append(b)
			if not changed:
				return res
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		d = dict()
		arr = []
		key = []
		for i in range(0, len(status)):
			arr.append(-1)
			key.append(-1)
			d[i] = [status[i], candies[i], keys[i], containedBoxes[i]]
			if status[i] == 1:
				key[-1] = 1
		c = 0
		res = []
		while 1 != -1:
			tmp = []
			for x in initialBoxes:
				if arr[x] == -1 and key[x] == 1:
					arr[x] = 1
					c += d[x][1]
					for y in d[x][2]:
						key[y] = 1
					for y in d[x][3]:
						if key[y] == 1:
							tmp.append(y)
						else:
							res.append(y)
				elif key[x] == -1:
					res.append(x)
			initialBoxes = []
			for y in res:
				if key[y] == 1 and arr[y] == -1:
					initialBoxes.append(y)
			initialBoxes += tmp
			if initialBoxes == []:
				break
		return c


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		s = [b for b in initialBoxes if status[b]]
		found_boxes = set([b for b in initialBoxes if not status[b]])
		r = 0
		while s:
			box = s.pop()
			r += candies[box]
			for key in keys[box]:
				status[key] = 1
			tbr = set()
			for b in found_boxes:
				if status[b]:
					s.append(b)
					tbr.add(b)
			found_boxes -= tbr
			for child in containedBoxes[box]:
				if status[child]:
					s.append(child)
				else:
					found_boxes.add(child)
		return r


class Box:

	def __init__(self, status, candies, keys, boxes):
		self.status = status
		self.candies = candies
		self.keys = keys
		self.containedBoxes = boxes

def openboxes(unopened, keys, Q):
	for u in unopened:
		if u in keys:
			Q.append(u)
			unopened.remove(u)

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		mykeys = []
		unopened = []
		candySum = 0
		Q = []
		for i in initialBoxes:
			mykeys.extend(keys[i])
			if status[i] == 1:
				Q.append(i)
			else:
				unopened.append(i)
		openboxes(unopened, mykeys, Q)
		while Q != []:
			box = Q.pop(0)
			candySum += candies[box]
			for b in containedBoxes[box]:
				mykeys.extend(keys[b])
				if status[b] == 1:
					Q.append(b)
				else:
					unopened.append(b)
			openboxes(unopened, mykeys, Q)
		return candySum


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		boxes = set(initialBoxes)
		queue = collections.deque()
		for box in boxes:
			if status[box] == 1:
				queue.append(box)
		ans = 0
		seen = set()
		while queue:
			box = queue.popleft()
			if box not in seen:
				seen.add(box)
				ans += candies[box]
			for i in containedBoxes[box]:
				boxes.add(i)
				if status[i] == 1:
					queue.append(i)
			for j in keys[box]:
				if status[j] == 0 and j in boxes:
					queue.append(j)
				status[j] = 1
		return ans


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		found = [0] * len(status)
		hasKeys = status
		queue = collections.deque()
		for box in initialBoxes:
			found[box] = 1
			if hasKeys[box]:
				queue.append(box)
		res = 0
		while queue:
			box = queue.popleft()
			res += candies[box]
			for t in containedBoxes[box]:
				found[t] = 1
				if hasKeys[t]:
					queue.append(t)
			for t in keys[box]:
				if not hasKeys[t] and found[t]:
					queue.append(t)
				hasKeys[t] = 1
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		totalBox = len(status)
		gotBoxes = set(initialBoxes)
		i = 0
		ans = 0
		visited = set()
		while i < len(initialBoxes):
			boxNow = initialBoxes[i]
			if boxNow not in visited:
				if status[boxNow] == 1:
					visited.add(boxNow)
					ans += candies[boxNow]
					for newBox in containedBoxes[boxNow]:
						if status[newBox] == 1:
							initialBoxes.append(newBox)
						else:
							gotBoxes.add(newBox)
					for keyBox in keys[boxNow]:
						status[keyBox] = 1
						if keyBox in gotBoxes:
							initialBoxes.append(keyBox)
							gotBoxes.remove(keyBox)
				else:
					gotBoxes.add(boxNow)
			i += 1
		return ans


class Solution:

	def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
		boxes = set(initialBoxes)
		bfs = [i for i in boxes if status[i]]
		for i in bfs:
			for j in containedBoxes[i]:
				boxes.add(j)
				if status[j]:
					bfs.append(j)
			for j in keys[i]:
				if status[j] == 0 and j in boxes:
					bfs.append(j)
				status[j] = 1
		return sum((candies[i] for i in bfs))


from collections import deque

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		visited = set(initialBoxes)
		reachable = set()
		deq = deque(initialBoxes)
		candy_cnt = 0
		while len(deq) > 0:
			box = deq.popleft()
			candy_cnt += candies[box]
			for cb in containedBoxes[box]:
				reachable.add(cb)
				if cb not in visited and status[cb] == 1:
					deq.append(cb)
					visited.add(cb)
			for key in keys[box]:
				status[key] = 1
				if key not in visited and key in reachable:
					deq.append(key)
					visited.add(key)
		return candy_cnt


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		foundBoxes = set(initialBoxes)
		openBoxes = [box for box in foundBoxes if status[box] == 1]
		for i in openBoxes:
			for x in containedBoxes[i]:
				foundBoxes.add(x)
				if status[x] == 1:
					openBoxes.append(x)
			for x in keys[i]:
				if status[x] == 0 and x in foundBoxes:
					openBoxes.append(x)
				status[x] = 1
		return sum([candies[i] for i in openBoxes])


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		N = len(status)
		queue = list()
		unopened = set()
		for i in initialBoxes:
			if status[i] == 1:
				queue.append(i)
			else:
				unopened.add(i)
		candiesCount = 0
		while len(queue) > 0:
			top = queue.pop(0)
			candiesCount += candies[top]
			for k in keys[top]:
				status[k] = 1
				if {k}.issubset(unopened):
					queue.append(k)
					unopened.remove(k)
			for c in containedBoxes[top]:
				if status[c] == 1:
					queue.append(c)
				else:
					unopened.add(c)
		return candiesCount


from collections import deque

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		q = deque(initialBoxes)
		ownedkeys = set()
		allkz = set()
		for k in keys:
			for l in k:
				allkz.add(l)
		opened = set()
		for (i, b) in enumerate(status):
			if not b and i not in allkz:
				opened.add(i)
		res = 0
		while q:
			curBox = q.popleft()
			if curBox not in opened:
				if status[curBox] or curBox in ownedkeys:
					opened.add(curBox)
					for k in keys[curBox]:
						ownedkeys.add(k)
					res += candies[curBox]
					q += containedBoxes[curBox]
				else:
					q.append(curBox)
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		n = len(status)
		boxes = []
		unboxes = set()
		for b in initialBoxes:
			if status[b]:
				boxes.append(b)
			else:
				unboxes.add(b)
		visited = set()
		got = 0
		while boxes:
			ns = set()
			for box in boxes:
				if box not in visited:
					got += candies[box]
					visited.add(box)
				for key in keys[box]:
					status[key] |= 1
			for box in boxes:
				for adj in containedBoxes[box]:
					unboxes.add(adj)
			newBoxes = set()
			for box in unboxes:
				if status[box] and box not in visited:
					ns.add(box)
					newBoxes.add(box)
			for box in newBoxes:
				unboxes.remove(box)
			boxes = list(ns)
		return got


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		n = len(status)
		hold = initialBoxes
		res = 0
		key = set()
		flag = True
		while flag:
			nxt = []
			flag = False
			for i in range(len(hold)):
				cur = hold.pop()
				if status[cur] == 1 or (status[cur] == 0 and cur in key):
					flag = True
					res += candies[cur]
					for k in keys[cur]:
						key.add(k)
					for b in containedBoxes[cur]:
						nxt.append(b)
				else:
					nxt.append(cur)
			hold = nxt
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		total_candies = 0
		open_boxes = [box for box in initialBoxes if status[box] == 1]
		locked_boxes = [box for box in initialBoxes if status[box] == 0]
		obtained_keys = set([])
		while len(open_boxes):
			box = open_boxes.pop()
			total_candies += candies[box]
			for key in keys[box]:
				if key in locked_boxes:
					locked_boxes.remove(key)
					open_boxes.append(key)
				else:
					obtained_keys.add(key)
			for cbox in containedBoxes[box]:
				if status[cbox] == 1 or cbox in obtained_keys:
					open_boxes.append(cbox)
				else:
					locked_boxes.append(cbox)
		return total_candies


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		(currkeys, ret, taken) = (set(), 0, [0] * len(status))
		q = collections.deque(initialBoxes)
		while q:
			l = len(q)
			opened = False
			for _ in range(l):
				curr = q.popleft()
				taken[curr] = 1
				if curr not in currkeys and status[curr] == 0:
					q.append(curr)
				else:
					opened = True
					ret += candies[curr]
					if keys[curr]:
						currkeys |= set([key for key in keys[curr]])
					for b in containedBoxes[curr]:
						if not taken[b]:
							q.append(b)
			if not opened:
				break
		return ret


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		if not initialBoxes:
			return 0
		unused_keys = set()
		boxes = set([i for i in initialBoxes if status[i] == 0])
		Q = collections.deque([i for i in initialBoxes if status[i] == 1])
		res = 0
		while Q:
			cur = Q.popleft()
			res += candies[cur]
			for k in keys[cur]:
				if k in boxes:
					Q.append(k)
					boxes.discard(k)
				else:
					unused_keys.add(k)
			for b in containedBoxes[cur]:
				if b in unused_keys or status[b] == 1:
					Q.append(b)
					unused_keys.discard(b)
				else:
					boxes.add(b)
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		N = len(status)
		scores = [0] * N
		for i in range(N):
			scores[i] += status[i]
		level = []
		for b in initialBoxes:
			scores[b] += N + 1
			if scores[b] >= N + 2:
				level.append(b)
				scores[b] = -sys.maxsize
		res = 0
		while level:
			n_level = []
			for b in level:
				res += candies[b]
				for k in containedBoxes[b]:
					scores[k] += N + 1
					if scores[k] >= N + 2:
						n_level.append(k)
						scores[k] = -sys.maxsize
				for k in keys[b]:
					scores[k] += 1
					if scores[k] >= N + 2:
						n_level.append(k)
						scores[k] = -sys.maxsize
			level = n_level
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		if not initialBoxes:
			return 0
		visited = set()
		boxes = set()
		keys_found = set()
		n_candies = 0
		opn = []
		for i in initialBoxes:
			if status[i] != 1:
				boxes.add(i)
			else:
				opn.append(i)
		initialBoxes = opn
		while initialBoxes:
			i = initialBoxes.pop(0)
			n_candies += candies[i]
			visited.add(i)
			if keys[i] != []:
				for j in keys[i]:
					keys_found.add(j)
			if containedBoxes[i] != []:
				for c in containedBoxes[i]:
					if status[c] == 1:
						initialBoxes.append(c)
					else:
						boxes.add(c)
			for k in boxes:
				if k in visited:
					continue
				if k in keys_found:
					initialBoxes.append(k)
					visited.add(k)
		return n_candies


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		ret = 0
		n = len(status)
		available_to_open = [box for box in initialBoxes if status[box]]
		reachable_boxes = set([box for box in initialBoxes if not status[box]])
		while len(available_to_open) > 0:
			box = available_to_open.pop()
			if status[box] == 2:
				continue
			ret += candies[box]
			status[box] = 2
			for containedBox in containedBoxes[box]:
				reachable_boxes.add(containedBox)
			for key in keys[box]:
				if status[key] == 0:
					status[key] = 1
			for containedBox in containedBoxes[box]:
				if status[containedBox] == 1:
					available_to_open.append(containedBox)
			for key in keys[box]:
				if key in reachable_boxes:
					available_to_open.append(key)
		return ret
		return ret


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		open_box = []
		close_box = set()
		key_set = set([i for i in range(len(status)) if status[i] == 1])
		visited = [False for _ in range(len(status))]
		count = 0
		for box in initialBoxes:
			if status[box] == 1:
				open_box.append(box)
			else:
				close_box.add(box)
		while open_box:
			box = open_box.pop()
			visited[box] = True
			count += candies[box]
			for key in keys[box]:
				key_set.add(key)
			for c_box in containedBoxes[box]:
				if visited[c_box]:
					continue
				else:
					close_box.add(c_box)
			for key in key_set:
				if key in close_box:
					open_box.append(key)
					close_box.remove(key)
		return count


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		q = collections.deque()
		keys_set = set([i for i in range(len(status)) if status[i] == 1])
		boxes_set = set(initialBoxes[:])
		for box in initialBoxes:
			if box in keys_set:
				q.append(box)
		res = 0
		visited = set()
		while q:
			boxi = q.popleft()
			if boxi in visited:
				continue
			else:
				visited.add(boxi)
				res += candies[boxi]
			for nei in containedBoxes[boxi]:
				if nei in keys_set:
					q.append(nei)
				boxes_set.add(nei)
			for key in keys[boxi]:
				if key in boxes_set and key not in keys_set:
					q.append(key)
				keys_set.add(key)
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		locked_boxes = set()
		unused_keys = set()
		candy_count = 0
		cur_box = []
		for box in initialBoxes:
			if status[box] or box in unused_keys:
				candy_count += candies[box]
				for i in keys[box]:
					if not status[i]:
						if i not in locked_boxes:
							unused_keys.add(i)
						else:
							locked_boxes.remove(i)
							cur_box.append(i)
				for i in containedBoxes[box]:
					if not status[i] and i not in unused_keys:
						locked_boxes.add(i)
					else:
						cur_box.append(i)
			else:
				locked_boxes.add(box)
		while cur_box:
			box = cur_box.pop()
			candy_count += candies[box]
			for i in keys[box]:
				if not status[i]:
					if i not in locked_boxes:
						unused_keys.add(i)
					else:
						locked_boxes.remove(i)
						cur_box.append(i)
			for i in containedBoxes[box]:
				if not status[i] and i not in unused_keys:
					locked_boxes.add(i)
				else:
					cur_box.append(i)
					if i in unused_keys:
						unused_keys.remove(i)
			if box in unused_keys:
				unused_keys.remove(box)
		return candy_count


class Solution:

	def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
		n = len(status)
		access = [0] * n
		source = []
		visited = set()
		for i in initialBoxes:
			access[i] = 1
			visited.add(i)
			source.append(i)
		ans = 0
		while source:
			i = source.pop()
			ans += candies[i]
			for j in containedBoxes[i]:
				access[j] = 1
			for j in keys[i]:
				status[j] = 1
			for j in containedBoxes[i]:
				if j not in visited and status[j]:
					visited.add(j)
					source.append(j)
			for j in keys[i]:
				if j not in visited and access[j]:
					visited.add(j)
					source.append(j)
		return ans


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		self.keys_found = set()
		self.boxes_found = set()
		self.boxes_found.update(initialBoxes)
		n = len(status)
		visited = [0] * n
		for box in initialBoxes:
			self.dfs(box, keys, containedBoxes, visited)
		ans = 0
		for i in range(n):
			if i in self.boxes_found and (i in self.keys_found or status[i] == 1):
				ans += candies[i]
		return ans

	def dfs(self, cur, keys, containedBoxes, visited):
		if visited[cur] == 1:
			return
		visited[cur] = 1
		boxes = containedBoxes[cur]
		self.keys_found.update(keys[cur])
		self.boxes_found.update(boxes)
		for box in boxes:
			self.dfs(box, keys, containedBoxes, visited)


from collections import deque

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		l = len(status)
		found = [False] * l
		run_q = deque([])
		wait_q = deque([])
		tmp_q = deque([])
		for box in initialBoxes:
			if status[box] == 1:
				run_q.append(box)
			else:
				wait_q.append(box)
		res = 0
		while run_q:
			box = run_q.popleft()
			res += candies[box]
			for key in keys[box]:
				status[key] = 1
			for found_box in containedBoxes[box]:
				wait_q.append(found_box)
			while wait_q:
				sleeping_box = wait_q.popleft()
				if status[sleeping_box] == 1:
					run_q.append(sleeping_box)
				else:
					tmp_q.append(sleeping_box)
			while tmp_q:
				wait_q.append(tmp_q.popleft())
		return res


import queue

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		ans = 0
		q = queue.Queue()
		notopen = set()
		op = set()
		for x in initialBoxes:
			q.put(x)
		while not q.empty():
			cur = q.get()
			if status[cur] == 1:
				ans += candies[cur]
				for k in keys[cur]:
					status[k] = 1
					if k in notopen and k not in op:
						q.put(k)
						op.add(k)
				for c in containedBoxes[cur]:
					q.put(c)
			else:
				notopen.add(cur)
		return ans


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		key_set = set()
		box_set = set()
		used = set()
		queue = collections.deque(initialBoxes)
		ans = 0
		while queue:
			box = queue.popleft()
			if box in used:
				continue
			if status[box] == 1 or box in key_set:
				used.add(box)
				if box in key_set:
					key_set.remove(box)
				if box in box_set:
					box_set.remove(box)
				ans += candies[box]
				for futureBox in containedBoxes[box]:
					box_set.add(futureBox)
				for futureKey in keys[box]:
					key_set.add(futureKey)
				for futureBox in box_set:
					if futureBox in key_set or status[futureBox] == 1:
						queue.append(futureBox)
			else:
				box_set.add(box)
		return ans


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		n = len(status)
		self.count = 0
		queue = collections.deque([i for i in initialBoxes if status[i] == 1])
		boxSet = set(initialBoxes)
		keySet = set((i for i in range(n) if status[i] == 1))
		opened = set()
		while queue:
			l = len(queue)
			for i in range(l):
				cur = queue.popleft()
				self.count += candies[cur]
				opened.add(cur)
				for key in keys[cur]:
					keySet.add(key)
					if key not in opened and key in boxSet and (key not in queue):
						queue.append(key)
				for box in containedBoxes[cur]:
					boxSet.add(box)
					if box not in opened and box in keySet and (box not in queue):
						queue.append(box)
		return self.count


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:

		def dfs(i):
			if i in visited:
				return
			if status[i] == 0:
				missedKey.add(i)
				return
			visited.add(i)
			self.ans += candies[i]
			for k in keys[i]:
				status[k] = 1
				if k in missedKey:
					missedKey.discard(k)
					dfs(k)
			for j in containedBoxes[i]:
				dfs(j)
		visited = set()
		missedKey = set()
		self.ans = 0
		for i in initialBoxes:
			dfs(i)
		return self.ans


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		q = collections.deque()
		keys_set = set()
		boxes_set = set()
		for box in initialBoxes:
			if status[box] == 1 or box in keys_set:
				q.append(box)
				for key in keys[box]:
					keys_set.add(key)
					if key in boxes_set:
						q.append(key)
						boxes_set.remove(key)
			else:
				boxes_set.add(box)
		res = 0
		visited = set()
		while q:
			boxi = q.popleft()
			if boxi in visited:
				continue
			else:
				visited.add(boxi)
				res += candies[boxi]
			for nei in containedBoxes[boxi]:
				if status[nei] == 1 or nei in keys_set:
					q.append(nei)
					for key in keys[nei]:
						keys_set.add(key)
						if key in boxes_set:
							q.append(key)
							boxes_set.remove(key)
				else:
					boxes_set.add(nei)
		return res


from collections import deque

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		n = len(status)
		(seen, queue, result) = ([False] * n, deque(initialBoxes), 0)
		num_locked = 0
		for box in initialBoxes:
			seen[box] = True
		while queue:
			box = queue.popleft()
			if not status[box]:
				queue.append(box)
				num_locked += 1
				if num_locked == len(queue):
					break
				continue
			num_locked = 0
			result += candies[box]
			for k in keys[box]:
				status[k] = 1
			for cb in containedBoxes[box]:
				if not seen[cb]:
					queue.append(cb)
					seen[cb] = True
		return result


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		if not initialBoxes:
			return 0
		if 1 not in status:
			return 0
		boxes = []
		result = 0
		while True:
			flag = False
			for b in initialBoxes:
				if status[b] == 1:
					flag = True
					result += candies[b]
					boxes += containedBoxes[b]
					for j in keys[b]:
						status[j] = 1
					initialBoxes.remove(b)
			initialBoxes += boxes
			boxes = []
			if not flag:
				break
		return result


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		(OPEN, CLOSED) = (1, 0)
		q = deque(initialBoxes)
		keys_obtained = set((i for i in range(len(status)) if status[i] == OPEN))
		count = 0
		while set(q) & keys_obtained:
			q2 = deque()
			while q:
				box = q.popleft()
				if box in keys_obtained:
					count += candies[box]
					keys_obtained |= set(keys[box])
					q.extend(containedBoxes[box])
				else:
					q2.append(box)
			q = q2
		return count


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		reached = set()
		visited = set()
		q = initialBoxes
		yummy = 0
		while q:
			new_q = []
			for box in q:
				reached.add(box)
				if status[box] and box not in visited:
					visited.add(box)
					new_q.extend(containedBoxes[box])
					new_q.extend((unlockedBox for unlockedBox in keys[box] if unlockedBox in reached))
					yummy += candies[box]
					for unlockedBox in keys[box]:
						status[unlockedBox] = 1
			q = new_q
		return yummy


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		q = collections.deque()
		for box in initialBoxes:
			q.append(box)
		keys_found = set()
		ans = 0
		found = True
		while q and found:
			size = len(q)
			found = False
			for _ in range(size):
				cur = q.popleft()
				if status[cur] == 0 and cur not in keys_found:
					q.append(cur)
				else:
					found = True
					ans += candies[cur]
					for box in containedBoxes[cur]:
						q.append(box)
					for key in keys[cur]:
						keys_found.add(key)
		return ans


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		queue = []
		visited = set()
		closedBoxes = set()
		foundedKeys = set()
		for box in initialBoxes:
			if status[box] == 1:
				queue.append(box)
			else:
				closedBoxes.add(box)
		res = 0
		while queue:
			cur = queue.pop(0)
			res += candies[cur]
			for box in containedBoxes[cur]:
				if status[box] == 1:
					queue.append(box)
				elif status[box] == 0 and box in foundedKeys:
					queue.append(box)
					foundedKeys.remove(box)
				else:
					closedBoxes.add(box)
			for key in keys[cur]:
				if key in closedBoxes:
					queue.append(key)
					closedBoxes.remove(key)
				else:
					foundedKeys.add(key)
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		boxes = set(initialBoxes)
		openedBox = set()
		bfs = [i for i in boxes if status[i]]
		while bfs:
			size = len(bfs)
			for _ in range(size):
				box = bfs.pop(0)
				openedBox.add(box)
				for eachContainedBox in containedBoxes[box]:
					if status[eachContainedBox]:
						bfs.append(eachContainedBox)
					boxes.add(eachContainedBox)
				for eachKey in keys[box]:
					if status[eachKey] == 0 and eachKey in boxes:
						bfs.append(eachKey)
					status[eachKey] = 1
		return sum((candies[box] for box in openedBox))


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		q = []
		res = 0
		vis = set()
		collected = set()
		for i in initialBoxes:
			q.append(i)
		while q:
			cur = q.pop(0)
			vis.add(cur)
			if status[cur] != 1 or cur in collected:
				continue
			res += candies[cur]
			collected.add(cur)
			for i in keys[cur]:
				status[i] = 1
				if i in vis:
					q.append(i)
			for j in containedBoxes[cur]:
				q.append(j)
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		(res, bcache, kcache) = (0, set(initialBoxes), set())
		for _ in range(1000):
			tmp = set()
			for b in bcache:
				if status[b] == 1 or b in kcache:
					tmp |= set(containedBoxes[b])
					kcache |= set(keys[b])
					res += candies[b]
				else:
					tmp.add(b)
			bcache = tmp
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		done = set()
		to_open = set()
		current_keys = set()
		opened = list()
		for box in initialBoxes:
			if status[box] == 1:
				opened.append(box)
			else:
				to_open.add(box)
		total = 0
		while opened:
			box = opened.pop()
			if box in done:
				continue
			total += candies[box]
			done.add(box)
			for openable in keys[box]:
				if openable in to_open:
					opened.append(openable)
					to_open.remove(openable)
				else:
					current_keys.add(openable)
			for contained in containedBoxes[box]:
				if status[contained] == 1:
					opened.append(contained)
				elif contained in current_keys:
					opened.append(contained)
					current_keys.remove(contained)
				else:
					to_open.add(contained)
		return total


class Solution:

	def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
		ret = 0
		collected_keys = set()
		opened = set()
		queue = initialBoxes
		while queue:
			cont = False
			for i in range(len(queue)):
				box_index = queue.pop(0)
				if status[box_index] or box_index in collected_keys:
					if box_index not in opened:
						cont = True
						opened.add(box_index)
						ret += candies[box_index]
						queue += containedBoxes[box_index]
						collected_keys.update(keys[box_index])
				else:
					queue.append(box_index)
			if not cont:
				break
		return ret


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		if len(initialBoxes) == 0:
			return 0
		else:
			boxdict = {}
			candysum = 0
			for initialbox in initialBoxes:
				boxdict[initialbox] = [0, 0]
			p = len(status) ** 2
			while p > 0:
				for i in range(len(containedBoxes)):
					if i in boxdict:
						for containedbox in containedBoxes[i]:
							boxdict[containedbox] = [0, 0]
						p -= 1
			for j in range(len(keys)):
				for boxedkeys in keys[j]:
					if boxedkeys in boxdict:
						boxdict[boxedkeys][1] = 1
			for l in range(len(status)):
				if status[l] == 1 and l in boxdict:
					boxdict[l][0] = 1
			for key in boxdict:
				if boxdict[key][0] == 1 and boxdict[key][1] == 1 or (boxdict[key][0] == 1 or boxdict[key][1] == 1):
					candysum += candies[key]
			return candysum


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		q = collections.deque()
		n = len(status)
		for i in initialBoxes:
			q.append(i)
		key = set()
		res = 0
		while q:
			length = len(q)
			hasOpen = False
			for i in range(length):
				box = q.popleft()
				if status[box] == 0 and box not in key:
					q.append(box)
				else:
					hasOpen = True
					res += candies[box]
					for k in keys[box]:
						key.add(k)
					for x in containedBoxes[box]:
						q.append(x)
			if not hasOpen:
				break
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		haskeys = status[:]
		seen = [0] * len(status)
		q = collections.deque()
		for box in initialBoxes:
			seen[box] = 1
			if haskeys[box]:
				q.append(box)
		res = 0
		while q:
			boxi = q.popleft()
			res += candies[boxi]
			for nei in containedBoxes[boxi]:
				seen[nei] = 1
				if haskeys[nei]:
					q.append(nei)
			for key in keys[boxi]:
				if seen[key] and haskeys[key] == 0:
					q.append(key)
				haskeys[key] = 1
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		maxCandy = 0
		keyset = set()
		numbox = len(status)
		q = list(initialBoxes)
		unopenedBOXES = []
		while q:
			for _ in range(len(q)):
				thisbox = q.pop(0)
				if status[thisbox] == 1 or thisbox in keyset:
					maxCandy += candies[thisbox]
					candies[thisbox] = 0
					for key in keys[thisbox]:
						keyset.add(key)
				else:
					unopenedBOXES.append(thisbox)
				for x in containedBoxes[thisbox]:
					q.append(x)
		for unopenedBOX in unopenedBOXES:
			if unopenedBOX in keyset:
				maxCandy += candies[unopenedBOX]
		return maxCandy


from collections import deque

class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		cur_queue = deque(initialBoxes)
		next_queue = deque([])
		key_set = set([])
		total = 0
		while True:
			temp_queue = cur_queue.copy()
			while temp_queue:
				c = temp_queue.popleft()
				if status[c] == 1 or c in key_set:
					key_set = key_set.union(keys[c])
					total += candies[c]
					for s in containedBoxes[c]:
						next_queue.append(s)
				else:
					next_queue.append(c)
			if cur_queue == next_queue:
				break
			cur_queue = next_queue
			next_queue = deque([])
		return total


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		maximum = 0
		cur = []
		closeddic = dict()
		size = 0
		for i in initialBoxes:
			if status[i] == 1:
				cur.append(i)
				size += 1
			else:
				closeddic[i] = 1
		consumed = dict()
		keysdic = dict()
		while size > 0:
			nex = []
			nsize = 0
			for i in cur:
				maximum += candies[i]
				consumed[i] = True
				for j in containedBoxes[i]:
					if (status[j] == 1 or j in keysdic) and j not in consumed:
						nex.append(j)
						nsize += 1
					elif status[j] == 0:
						closeddic[j] = 1
				for j in keys[i]:
					keysdic[j] = 1
					if j in closeddic and j not in consumed:
						del closeddic[j]
						nex.append(j)
						nsize += 1
			size = nsize
			cur = nex
		return maximum


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		keyHold = set([idx for (idx, b) in enumerate(status) if b == 1])
		boxHold = set(initialBoxes)
		opened = set()
		while True:
			flag = False
			newKey = set()
			newBox = set()
			for b in boxHold:
				if b in keyHold:
					opened.add(b)
					flag = True
					for k in keys[b]:
						newKey.add(k)
					for nb in containedBoxes[b]:
						if nb not in opened:
							newBox.add(nb)
			if not flag:
				break
			for k in newKey:
				keyHold.add(k)
			for b in newBox:
				boxHold.add(b)
			for b in opened:
				boxHold.discard(b)
		return sum([c for (idx, c) in enumerate(candies) if idx in opened])


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		open = initialBoxes
		x_keys = set()
		locked = set()
		result = 0
		seen = set()
		while len(open) != 0:
			i = open.pop(0)
			if i in seen:
				continue
			for key in keys[i]:
				x_keys.add(key)
			for box in containedBoxes[i]:
				if box in x_keys or status[box] == 1:
					open.append(box)
				else:
					locked.add(box)
			for box in locked:
				if box in x_keys:
					open.append(box)
			result += candies[i]
			seen.add(i)
		return result


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		parent = collections.defaultdict(int)
		for (i, row) in enumerate(containedBoxes):
			for j in row:
				parent[j] = i
		n = len(status)
		bfs = collections.deque([(i, False) for i in initialBoxes])
		res = 0
		seen = set()
		while bfs:
			(box, st) = bfs.popleft()
			if box in seen:
				continue
			if status[box] == 0:
				if st:
					return res
				bfs.append((box, True))
				continue
			seen.add(box)
			res += candies[box]
			for key in keys[box]:
				status[key] = 1
			for cbox in containedBoxes[box]:
				bfs.append((cbox, False))
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		q = initialBoxes
		has_key = [0] * len(status)
		has_open = [0] * len(status)
		res = 0
		while q:
			qq = []
			for s in q:
				if status[s] or has_key[s]:
					res += candies[s]
					has_open[s] = 1
					for b in containedBoxes[s]:
						if has_open[b]:
							continue
						qq.append(b)
					for k in keys[s]:
						has_key[k] = 1
				else:
					qq.append(s)
			if tuple(qq) == tuple(q):
				break
			(q, qq) = (qq, [])
		return res


class Solution:

	def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
		open_boxes = set()
		closed_boxes = set()
		for b in initialBoxes:
			if status[b]:
				open_boxes.add(b)
			else:
				closed_boxes.add(b)
		total_candies = 0
		while len(open_boxes) > 0:
			b = open_boxes.pop()
			total_candies += candies[b]
			for key in keys[b]:
				status[key] = 1
				if key in closed_boxes:
					closed_boxes.remove(key)
					open_boxes.add(key)
			for bb in containedBoxes[b]:
				if status[bb]:
					open_boxes.add(bb)
				else:
					closed_boxes.add(bb)
		return total_candies