A kingdom consists of a king, his children, his grandchildren, and so on. Every once in a while, someone in the family dies or a child is born.
The kingdom has a well-defined order of inheritance that consists of the king as the first member. Let's define the recursive function Successor(x, curOrder), which given a person x and the inheritance order so far, returns who should be the next person after x in the order of inheritance.
Successor(x, curOrder):
    if x has no children or all of x's children are in curOrder:
        if x is the king return null
        else return Successor(x's parent, curOrder)
    else return x's oldest child who's not in curOrder

For example, assume we have a kingdom that consists of the king, his children Alice and Bob (Alice is older than Bob), and finally Alice's son Jack.

In the beginning, curOrder will be ["king"].
Calling Successor(king, curOrder) will return Alice, so we append to curOrder to get ["king", "Alice"].
Calling Successor(Alice, curOrder) will return Jack, so we append to curOrder to get ["king", "Alice", "Jack"].
Calling Successor(Jack, curOrder) will return Bob, so we append to curOrder to get ["king", "Alice", "Jack", "Bob"].
Calling Successor(Bob, curOrder) will return null. Thus the order of inheritance will be ["king", "Alice", "Jack", "Bob"].

Using the above function, we can always obtain a unique order of inheritance.
Implement the ThroneInheritance class:

ThroneInheritance(string kingName) Initializes an object of the ThroneInheritance class. The name of the king is given as part of the constructor.
void birth(string parentName, string childName) Indicates that parentName gave birth to childName.
void death(string name) Indicates the death of name. The death of the person doesn't affect the Successor function nor the current inheritance order. You can treat it as just marking the person as dead.
string[] getInheritanceOrder() Returns a list representing the current order of inheritance excluding dead people.

 
Example 1:
Input
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
Output
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]

Explanation
ThroneInheritance t= new ThroneInheritance("king"); // order: king
t.birth("king", "andy"); // order: king > andy
t.birth("king", "bob"); // order: king > andy > bob
t.birth("king", "catherine"); // order: king > andy > bob > catherine
t.birth("andy", "matthew"); // order: king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // order: king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "alex", "asha", "catherine"]

 
Constraints:

1 <= kingName.length, parentName.length, childName.length, name.length <= 15
kingName, parentName, childName, and name consist of lowercase English letters only.
All arguments childName and kingName are distinct.
All name arguments of death will be passed to either the constructor or as childName to birth first.
For each call to birth(parentName, childName), it is guaranteed that parentName is alive.
At most 105 calls will be made to birth and death.
At most 10 calls will be made to getInheritanceOrder.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: class ThroneInheritance:
    def __init__(self, kingName: str):
    def birth(self, parentName: str, childName: str) -> None:
    def death(self, name: str) -> None:
    def getInheritanceOrder(self) -> List[str]:
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

Solutions:
class ThroneInheritance:

	def __init__(self, kingName: str):
		self.graph = collections.defaultdict(list)
		self.deaths = set()
		self.root = kingName

	def birth(self, parentName: str, childName: str) -> None:
		self.graph[parentName].append(childName)

	def death(self, name: str) -> None:
		self.deaths.add(name)

	def inorder(self, root, res):
		if root not in self.deaths:
			res.append(root)
		children = self.graph[root]
		for child in children:
			self.inorder(child, res)

	def getInheritanceOrder(self) -> List[str]:
		res = []
		self.inorder(self.root, res)
		return res


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.graph = collections.defaultdict(list)
		self.root = kingName
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.graph[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def dfs(self, name, arr):
		if name not in self.dead:
			arr.append(name)
		for nei in self.graph[name]:
			self.dfs(nei, arr)
		return arr

	def getInheritanceOrder(self) -> List[str]:
		ans = []
		self.dfs(self.root, ans)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kName = kingName
		self.dead = set()
		self.cmap = {}

	def birth(self, parentName: str, childName: str) -> None:
		cmap = self.cmap
		if parentName not in self.cmap:
			cmap[parentName] = []
		cmap[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		res = []
		dfs(self.cmap, self.dead, self.kName, res)
		return res

def dfs(cmap, deaths, curr, res):
	if curr == None:
		return
	if curr not in deaths:
		res.append(curr)
	if curr in cmap:
		for child in cmap[curr]:
			dfs(cmap, deaths, child, res)


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kn = kingName
		self.get_child = {}
		self.get_parent = {}
		self.is_dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		if parentName in self.get_child:
			self.get_child[parentName][0].append(childName)
		else:
			self.get_child[parentName] = ([childName], 0)
		self.get_parent[childName] = parentName

	def death(self, name: str) -> None:
		self.is_dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		cur_order = [self.kn]
		cur_order_set = set()

		def successor(x):
			child = []
			start_index = 0
			if x in self.get_child:
				(child, start_index) = self.get_child[x]
			if len(child) == 0 or all([c in cur_order_set for c in child]):
				if x == self.kn:
					return None
				else:
					return successor(self.get_parent[x])
			else:
				for i in range(start_index, len(child)):
					c = child[i]
					if c not in cur_order_set:
						return c
			assert False
			return None
		while cur_order[-1]:
			s = successor(cur_order[-1])
			cur_order.append(s)
			cur_order_set.add(s)
		final_cur_order = []
		for co in cur_order:
			if co and co not in self.is_dead:
				final_cur_order.append(co)
		return final_cur_order


class Node:

	def __init__(self, name):
		self.val = name
		self.children = []
		self.alive = True

	def birth(self, child):
		self.children.append(child)

	def death(self):
		self.alive = False

	def check_alive(self):
		return self.alive

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Node(kingName)
		self.d = dict()
		self.d[kingName] = self.king

	def birth(self, parentName: str, childName: str) -> None:
		child = Node(childName)
		self.d[childName] = child
		self.d[parentName].birth(child)

	def death(self, name: str) -> None:
		self.d[name].death()

	def getInheritanceOrder(self) -> List[str]:
		rtv = []
		todo = []
		todo.append(self.king)
		while todo:
			t = todo.pop()
			if t.check_alive():
				rtv.append(t.val)
			for c in t.children[::-1]:
				todo.append(c)
		return rtv


class Node:

	def __init__(self, name):
		self.name = name
		self.is_dead = False
		self.children = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king_name = kingName
		self.nodes = {kingName: Node(kingName)}

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.nodes[parentName]
		child = Node(childName)
		parent.children.append(child)
		self.nodes[childName] = child

	def death(self, name: str) -> None:
		node = self.nodes[name]
		node.is_dead = True

	def getInheritanceOrder(self) -> List[str]:
		acc = []

		def getInheritanceOrderRecursive(node):
			if not node.is_dead:
				acc.append(node.name)
			for child in node.children:
				getInheritanceOrderRecursive(child)
		getInheritanceOrderRecursive(self.nodes[self.king_name])
		return acc


class ThroneInheritance:
	root = ''
	children = {}
	dead = {}

	def __init__(self, kingName: str):
		self.root = kingName
		self.dead[self.root] = False
		self.children = defaultdict(list)

	def birth(self, parentName: str, childName: str) -> None:
		self.children[parentName].append(childName)
		self.dead[parentName] = False
		self.dead[childName] = False

	def death(self, name: str) -> None:
		self.dead[name] = True

	def getInheritanceOrder(self) -> List[str]:
		res = []
		tosee = []
		tosee.append(self.root)
		while len(tosee) != 0:
			cur = tosee[0]
			tosee.pop(0)
			if self.dead[cur] == False:
				res.append(cur)
			for item in reversed(self.children[cur]):
				tosee.insert(0, item)
		return res


from collections import defaultdict

class Node:

	def __init__(self, name):
		self.name = name
		self.childs = []
		self.live = 1

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.p2cList = defaultdict(Node)
		self.p2cList[kingName] = self.root

	def birth(self, parentName: str, childName: str) -> None:
		child = Node(childName)
		self.p2cList[parentName].childs.append(child)
		self.p2cList[childName] = child

	def death(self, name: str) -> None:
		self.p2cList[name].live = 0

	def getInheritanceOrder(self) -> List[str]:
		res = []
		cur = self.root
		self.helper(res, cur)
		return res

	def helper(self, res, cur):
		if cur.live == 1:
			res.append(cur.name)
		if not cur.childs:
			return
		for childname in cur.childs:
			self.helper(res, childname)


class ThroneInheritance:
	allNames = {}

	def __init__(self, kingName: str):
		self.name = kingName
		self.alive = True
		self.children = []
		self.allNames[kingName] = self

	def birth(self, parentName: str, childName: str) -> None:
		self.allNames[parentName].children += [ThroneInheritance(childName)]

	def death(self, name: str) -> None:
		self.allNames[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		answ = []
		if self.alive:
			answ += [self.name]
		for child in self.children:
			answ += child.getInheritanceOrder()
		return answ


from collections import defaultdict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.dead = set()
		self.members = defaultdict(list)
		self.king = kingName

	def birth(self, parentName: str, childName: str) -> None:
		self.members[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		inheritanceOrder = []

		def traverse(member):
			if member not in self.dead:
				inheritanceOrder.append(member)
			for child in self.members[member]:
				traverse(child)
		traverse(self.king)
		return inheritanceOrder


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.dead_set = set()
		self.children = collections.defaultdict(list)
		self.inheritance_order = []

	def birth(self, parentName: str, childName: str) -> None:
		self.children[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead_set.add(name)

	def successor(self, x):
		if x not in self.dead_set:
			self.inheritance_order.append(x)
		for child in self.children[x]:
			self.successor(child)

	def getInheritanceOrder(self) -> List[str]:
		self.successor(self.king)
		res = self.inheritance_order[:]
		self.inheritance_order = []
		return res


class Child:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.dead = False

def recursive(order):
	if not order.dead:
		out = [order.name]
	else:
		out = []
	for i in order.children:
		out += recursive(i)
	return out

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.order = Child(kingName)
		self.dict = {kingName: self.order}

	def birth(self, parentName: str, childName: str) -> None:
		b = Child(childName)
		self.dict[parentName].children.append(b)
		self.dict[childName] = b

	def death(self, name: str) -> None:
		self.dict[name].dead = True

	def getInheritanceOrder(self) -> List[str]:
		return recursive(self.order)


class Node:

	def __init__(self, name):
		self.children = []
		self.name = name

	def add_children(self, name):
		node = Node(name)
		self.children.append(node)
		return node

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.dead = set()
		self.lookup = dict()
		self.lookup[kingName] = self.root

	def birth(self, parentName: str, childName: str) -> None:
		self.lookup[childName] = self.lookup[parentName].add_children(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		results = []

		def dfs(x):
			nonlocal results
			if x.name not in self.dead:
				results.append(x.name)
			for y in x.children:
				dfs(y)
		dfs(self.root)
		return results


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.parent = {}
		self.child = {}
		self.dead = set([])

	def birth(self, parentName: str, childName: str) -> None:
		self.addToHash(self.parent, childName, parentName)
		self.addToHash(self.child, parentName, childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def succesor(self, name, curOrder):
		if self.child.get(name):
			for c in self.child.get(name):
				if c not in curOrder:
					return c
		if name == self.kingName:
			return None
		return self.succesor(self.parent[name][0], curOrder)

	def getInheritanceOrder(self) -> List[str]:
		res = []
		cur = self.kingName
		inOrder = set([])
		while cur:
			if cur not in self.dead:
				res.append(cur)
			inOrder.add(cur)
			cur = self.succesor(cur, inOrder)
		return res

	def addToHash(self, hsh, key, value):
		if hsh.get(key):
			hsh.get(key).append(value)
		else:
			hsh[key] = [value]


class Tree:

	def __init__(self, name):
		self.val = name
		self.descents = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.dic = {}
		self.dead = set()
		self.kingNode = Tree(kingName)
		self.dic[kingName] = self.kingNode

	def birth(self, parentName: str, childName: str) -> None:
		if parentName not in self.dic:
			node = Tree(parentName)
			self.dic[parentName] = node
		childNode = Tree(childName)
		self.dic[childName] = childNode
		self.dic[parentName].descents.append(childNode)

	def death(self, name: str) -> None:
		self.dead.add(self.dic[name])

	def output(self, root):
		if root not in self.dead:
			self.ans.append(root.val)
		for child in root.descents:
			self.output(child)

	def getInheritanceOrder(self) -> List[str]:
		self.ans = []
		self.output(self.kingNode)
		return self.ans


class Node:

	def __init__(self, name):
		self.name = name
		self.live = True
		self.children = []

	def death(self):
		self.live = False

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.d = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		self.d[childName] = Node(childName)
		self.d[parentName].children.append(self.d[childName])

	def death(self, name: str) -> None:
		self.d[name].death()

	def getInheritanceOrder(self) -> List[str]:

		def dfs(node, ans):
			if node.live:
				ans.append(node.name)
			for ch in node.children:
				dfs(ch, ans)
		ans = []
		dfs(self.root, ans)
		return ans


class Node:

	def __init__(self, name):
		self.name = name
		self.children = list()
		self.alive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.map = defaultdict(Node)
		self.map[kingName] = Node(kingName)
		self.parent = defaultdict(str)
		self.king = kingName
		self.curOrder = [kingName]

	def birth(self, parentName: str, childName: str) -> None:
		self.map[childName] = Node(childName)
		self.map[parentName].children.append(childName)
		self.parent[childName] = parentName

	def death(self, name: str) -> None:
		self.map[name].alive = False

	def Successor(self, x):
		flag = False
		for child in self.map[x].children:
			if child not in self.currSet:
				break
		else:
			flag = True
		if not self.map[x].children or flag:
			if x == self.king:
				return None
			else:
				return self.Successor(self.parent[x])
		else:
			for child in self.map[x].children:
				if child not in self.currSet:
					return child
			return None

	def getInheritanceOrder(self) -> List[str]:
		self.curOrder = []
		self.currSet = set()
		name = self.king
		while name:
			self.curOrder.append(name)
			self.currSet.add(name)
			name = self.Successor(name)
		return [a for a in self.curOrder if self.map[a].alive]


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.nation = defaultdict(list)
		self.king = kingName
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.nation[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def dfs(self, person):
		if person not in self.dead:
			self.ans.append(person)
		for child in self.nation[person]:
			self.dfs(child)

	def getInheritanceOrder(self) -> List[str]:
		self.ans = []
		self.dfs(self.king)
		return self.ans


from functools import lru_cache

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.pm = {}
		self.cm = {}
		self.p = {kingName: True}
		self.king = kingName
		self.cm[kingName] = []

	def birth(self, parentName: str, childName: str) -> None:
		self.pm[childName] = parentName
		self.cm[parentName].append(childName)
		self.cm[childName] = []
		self.p[childName] = True

	def death(self, name: str) -> None:
		self.p[name] = False

	def getInheritanceOrder(self) -> List[str]:
		x = self.king
		curOrder = [x]
		marked_childs = {}
		queue_childs = {}
		for (p, v) in self.cm.items():
			marked_childs[p] = set()
			queue_childs[p] = v[:]
		while True:
			res = self.successor(x, marked_childs, queue_childs)
			if res == None:
				break
			curOrder.append(res)
			x = res
		ans = []
		for p in curOrder:
			if self.p[p]:
				ans += [p]
		return ans

	def successor(self, x, marked_childs, queue_childs):
		if len(self.cm[x]) == 0 or len(queue_childs[x]) == 0:
			if self.king == x:
				return None
			else:
				return self.successor(self.pm[x], marked_childs, queue_childs)
		else:
			c = queue_childs[x].pop(0)
			marked_childs[x] = c
			return c


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.children = defaultdict(list)
		self.parent = {}
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.children[parentName].append(childName)
		self.parent[childName] = parentName

	def successor(self, name):
		for child in self.children[name]:
			if child not in self.order_set:
				self.order_set.add(child)
				self.curOrder.append(child)
				return child
		if name != self.kingName:
			return self.successor(self.parent[name])
		return None

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		self.curOrder = [self.kingName]
		self.order_set = set(self.curOrder)
		name = self.kingName
		while name:
			name = self.successor(name)
		return [name for name in self.curOrder if name not in self.dead]


from collections import defaultdict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.family = defaultdict(list)
		self.parents = {}
		self.dead = set()
		self.size = 1

	def birth(self, parentName: str, childName: str) -> None:
		self.family[parentName].append(childName)
		self.parents[childName] = parentName
		self.size += 1

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		ans = [self.king]
		pool = set(self.king)

		def sccesssor(x, curOrder):
			if self.family[x] == [] or set(self.family[x]) <= pool:
				if x == self.king:
					return
				else:
					sccesssor(self.parents[x], curOrder)
			else:
				for name in self.family[x]:
					if name not in pool:
						curOrder.append(name)
						pool.add(name)
						return
		for i in range(self.size - 1):
			if ans[-1] in self.dead:
				dead = ans.pop()
				sccesssor(dead, ans)
			else:
				sccesssor(ans[-1], ans)
		if ans[-1] in self.dead:
			ans.pop()
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.d = defaultdict(list)
		self.deads = set()
		self.k = kingName

	def birth(self, parentName: str, childName: str) -> None:
		self.d[parentName].append(childName)

	def death(self, name: str) -> None:
		self.deads.add(name)

	def getInheritanceOrder(self) -> List[str]:
		arr = []

		def getChildren(name):
			if name not in self.deads:
				arr.append(name)
			for child in self.d[name]:
				getChildren(child)
		getChildren(self.k)
		return arr


class Person(object):

	def __init__(self, name, p_name, live=True):
		self.name = name
		self.p_name = p_name
		self.live = live
		self.sibling = None
		self.first_child = None
		self.last_child = None

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.curOrder = [kingName]
		self.curOrder_pos = {}
		self.inherit_pos = float('inf')
		self.person_map = {}
		self.person_map[kingName] = Person(kingName, None)

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.person_map[parentName]
		children = parent.first_child
		if children == None:
			parent.first_child = Person(childName, parentName)
			self.person_map[childName] = parent.first_child
			parent.last_child = parent.first_child
		else:
			parent.last_child.sibling = Person(childName, parentName)
			parent.last_child = parent.last_child.sibling
			self.person_map[childName] = parent.last_child
		if parentName in self.curOrder_pos:
			self.inherit_pos = min(self.inherit_pos, self.curOrder_pos[parentName])

	def death(self, name: str) -> None:
		self.person_map[name].live = False

	def getInheritanceOrder(self) -> List[str]:

		def successor(person_map, x, curOrder, curOrder_pos):
			p = person_map[x]
			c = p.first_child
			o_c = None
			while c:
				if c.name not in curOrder_pos:
					o_c = c
					break
				c = c.sibling
			if not p.first_child or not o_c:
				return None if x == curOrder[0] else successor(person_map, p.p_name, curOrder, curOrder_pos)
			else:
				return o_c.name
		if self.inherit_pos != float('inf'):
			for i in range(self.inherit_pos + 1, len(self.curOrder)):
				del self.curOrder_pos[self.curOrder[i]]
			self.curOrder = self.curOrder[:self.inherit_pos + 1]
		nxt = successor(self.person_map, self.curOrder[-1], self.curOrder, self.curOrder_pos)
		while nxt:
			self.curOrder.append(nxt)
			self.curOrder_pos[nxt] = len(self.curOrder) - 1
			nxt = successor(self.person_map, nxt, self.curOrder, self.curOrder_pos)
		result = []
		for (i, x) in enumerate(self.curOrder):
			if self.person_map[x].live:
				result.append(x)
		self.inherit_pos = float('inf')
		return result


class Node:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.isAlive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Node(kingName)
		self.directory = {kingName: self.king}

	def birth(self, parentName: str, childName: str) -> None:
		parentnode = self.directory[parentName]
		childnode = Node(childName)
		parentnode.children.append(childnode)
		self.directory[childName] = childnode

	def death(self, name: str) -> None:
		self.directory[name].isAlive = False

	def getInheritanceOrder(self) -> List[str]:
		ans = []

		def dfs(node):
			if not node:
				return
			if node.isAlive:
				ans.append(node.name)
			for child in node.children:
				dfs(child)
		dfs(self.king)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.start = kingName
		self.deaths = {}
		self.relat = collections.defaultdict(list)
		self.relat[kingName] = []
		self.n = 1

	def birth(self, parentName: str, childName: str) -> None:
		self.relat[parentName].append(childName)
		self.n += 1

	def death(self, name: str) -> None:
		self.deaths[name] = True

	def getInheritanceOrder(self) -> List[str]:
		ret = []
		q = [self.start]
		while q:
			cur = q.pop()
			if cur not in self.deaths:
				ret.append(cur)
			for nxt in self.relat[cur][::-1]:
				q.append(nxt)
		return ret


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.parents = {}
		self.children = collections.defaultdict(list)
		self.dead = set()

	def Successor(self, x, cur_order):
		x_children = self.children.get(x, [])
		cand = None
		for c in x_children:
			if c not in cur_order:
				cand = c
				break
		if len(x_children) == 0 or cand is None:
			if x == self.king:
				return None
			else:
				return self.Successor(self.parents[x], cur_order)
		else:
			return cand

	def birth(self, parentName: str, childName: str) -> None:
		self.parents[childName] = parentName
		self.children[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		res = []
		suc = self.king
		cur_order = set([suc])
		while suc:
			if suc not in self.dead:
				res.append(suc)
			cur_order.add(suc)
			suc = self.Successor(suc, cur_order)
		return res


class Person:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.alive = True
		self.parent = None

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Person(kingName)
		self.people = {kingName: self.king}

	def successor(self, x, current_order):
		stack = [x]
		while len(stack) > 0:
			t = stack.pop()
			if t.alive:
				current_order.append(t)
			for i in t.children:
				stack.append(i)

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.people.get(parentName)
		child = Person(childName)
		self.people[childName] = child
		child.parent = parent
		parent.children = [child] + parent.children

	def death(self, name: str) -> None:
		p = self.people.get(name)
		p.alive = False

	def getInheritanceOrder(self) -> List[str]:
		result = []
		self.successor(self.king, result)
		return [i.name for i in result]


class people:

	def __init__(self, name):
		self.name = name
		self.son = []
		self.alive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = people(kingName)
		self.all_people = {}
		self.all_people[kingName] = self.king

	def birth(self, parentName: str, childName: str) -> None:
		self.all_people[childName] = people(childName)
		p = self.all_people[parentName]
		p.son.append(self.all_people[childName])

	def death(self, name: str) -> None:
		self.all_people[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		ans = []
		p = self.king
		stack = []
		while p or stack:
			if p.alive:
				ans.append(p.name)
			if p.son:
				for i in reversed(p.son[1:]):
					stack.append(i)
				p = p.son[0]
			elif stack:
				p = stack.pop()
			else:
				p = None
		return ans


class Node:

	def __init__(self, val):
		self.val = val
		self.child = None
		self.next = None
		self.prev = None
		self.parent = None

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.throne = Node(kingName)
		self.nodes = dict()
		self.nodes[kingName] = self.throne

	def birth(self, parentName: str, childName: str) -> None:
		node = self.nodes[parentName]
		if node.child:
			child = node.child
			while child.__next__ != None:
				child = child.__next__
			child.next = Node(childName)
			child.next.prev = child
			child.next.parent = node
			self.nodes[childName] = child.__next__
		else:
			node.child = Node(childName)
			node.child.parent = node
			self.nodes[childName] = node.child

	def death(self, name: str) -> None:
		del self.nodes[name]

	def getInheritanceOrder(self) -> List[str]:
		order = []
		if not self.throne:
			return None
		stack = [self.throne]
		while stack:
			curr = stack.pop()
			if curr.val in self.nodes:
				order.append(curr.val)
			if curr.__next__:
				stack.append(curr.__next__)
			if curr.child:
				stack.append(curr.child)
		return order


class Node:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.alive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.people = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		child = Node(childName)
		self.people[parentName].children.append(child)
		self.people[childName] = child

	def death(self, name: str) -> None:
		self.people[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		res = []
		self.helper(self.root, res)
		return res

	def helper(self, root, res):
		if root.alive:
			res.append(root.name)
		if not root.children:
			return
		for child in root.children:
			self.helper(child, res)


class people:

	def __init__(self, name):
		self.name = name
		self.alive = True
		self.children = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.dic = {}
		self.dic[kingName] = people(kingName)

	def birth(self, parentName: str, childName: str) -> None:
		child = people(childName)
		self.dic[childName] = child
		self.dic[parentName].children.append(child)

	def death(self, name: str) -> None:
		self.dic[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		order = self.dfs(self.dic[self.kingName])
		res = []
		for o in order:
			if o.alive is True:
				res.append(o.name)
		return res

	def dfs(self, cur):
		res = []
		res.append(cur)
		for child in cur.children:
			temp = self.dfs(child)
			res += temp
		return res


class ThroneInheritance:
	import collections

	def __init__(self, kingName: str):
		self.king_name = kingName
		self.dead = set([])
		self.children = collections.defaultdict(list)
		self.parent = {}

	def birth(self, parentName: str, childName: str) -> None:
		self.children[parentName].append(childName)
		self.parent[childName] = parentName

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		order = [self.king_name]
		order_set = set(order)

		def successor(x):
			ys = [y for y in self.children[x] if y not in order_set]
			if not ys:
				if x == self.king_name:
					return None
				return successor(self.parent[x])
			y = ys[0]
			order.append(y)
			order_set.add(y)
			return y
		p = successor(self.king_name)
		while p:
			p = successor(p)
		return [name for name in order if name not in self.dead]


import copy

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.parent = collections.defaultdict(list)
		self.children = collections.defaultdict(list)
		self.king = kingName
		self.deathList = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.parent[childName].append(parentName)
		self.children[parentName].append(childName)

	def death(self, name: str) -> None:
		self.deathList.add(name)

	def getInheritanceOrder(self) -> List[str]:
		order = [self.king]
		current = self.king
		c = copy.deepcopy(self.children)
		p = copy.copy(self.parent)

		def Successor(x, curOrder):
			if x not in c or len(c[x]) == 0:
				if x == self.king:
					return None
				else:
					return Successor(p[x][0], curOrder)
			newx = c[x].pop(0)
			curOrder.append(newx)
			return newx
		while current:
			current = Successor(current, order)
		if not self.deathList:
			return order
		else:
			neworder = []
			for name in order:
				if name not in self.deathList:
					neworder.append(name)
			return neworder


class Node:

	def __init__(self, name):
		self.name = name
		self.children = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.hm = {kingName: self.root}
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		pnode = self.hm[parentName]
		cNode = Node(childName)
		self.hm[childName] = cNode
		pnode.children.append(cNode)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		res = []

		def dfs(node):
			if node.name not in self.dead:
				res.append(node.name)
			for child in node.children:
				dfs(child)
		dfs(self.root)
		return res


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.parent = defaultdict(str)
		self.children = defaultdict(list)
		self.king = kingName
		self.order = []
		self.orderset = set()
		self.dead = set()

	def birth(self, p: str, c: str) -> None:
		self.parent[c] = p
		self.children[p].append(c)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		self.order = [self.king]
		self.orderset = set([self.king])
		while self.getNext(self.order[-1]):
			temp = self.getNext(self.order[-1])
			self.order.append(temp)
			self.orderset.add(temp)
		res = []
		for ele in self.order:
			if ele not in self.dead:
				res.append(ele)
		return res

	def getNext(self, cur):
		if not self.children[cur] or self.check(cur):
			if cur == self.king:
				return None
			else:
				return self.getNext(self.parent[cur])
		else:
			for child in self.children[cur]:
				if child not in self.orderset:
					return child

	def check(self, cur):
		for child in self.children[cur]:
			if child not in self.orderset:
				return False
		return True


class Family:

	def __init__(self, name):
		self.dead = False
		self.children = []
		self.name = name

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.family_map = {}
		member = Family(kingName)
		self.family_map[kingName] = member
		self.king = member

	def birth(self, parentName: str, childName: str) -> None:
		member = self.family_map[parentName]
		child = Family(childName)
		member.children.append(child)
		self.family_map[childName] = child

	def death(self, name: str) -> None:
		member = self.family_map[name]
		member.dead = True

	def getInheritanceOrder(self) -> List[str]:
		inheritance = []
		stack = [self.king]
		while len(stack):
			member = stack.pop()
			for child in member.children[::-1]:
				stack.append(child)
			if not member.dead:
				inheritance.append(member.name)
		return inheritance


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.descs = defaultdict(list)
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.descs[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		stack = [self.king]
		ans = []
		while stack:
			heir = stack.pop()
			if heir not in self.dead:
				ans.append(heir)
			stack += self.descs[heir][::-1]
		return ans


class Node(object):

	def __init__(self, name, parent=''):
		self.name = name
		self.parent = parent
		self.children = []

	def addChild(self, child):
		self.children.append(child)

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.node = {kingName: self.root}
		self.deaths = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.node[parentName].addChild(childName)
		self.node[childName] = Node(childName, parentName)

	def death(self, name: str) -> None:
		self.deaths.add(name)

	def getInheritanceOrder(self) -> List[str]:
		order = [self.root.name]
		seen = set(order)

		def successor(nodeName):
			node = self.node[nodeName]
			if not node.children or all((c in seen for c in node.children)):
				if nodeName == self.root.name:
					return
				return successor(node.parent)
			for c in node.children:
				if c not in seen:
					seen.add(c)
					order.append(c)
					return c
		while (name := successor(order[-1])):
			pass
		return [o for o in order if o not in self.deaths]


class TreeNode:

	def __init__(self, val=None):
		self.val = val
		self.children = []
		self.parent = None

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.dic = {}
		self.root = TreeNode(kingName)
		self.dic[kingName] = self.root
		self.dead = {}

	def birth(self, parentName: str, childName: str) -> None:
		parent_node = self.dic[parentName]
		child_node = TreeNode(childName)
		child_node.parent = parent_node
		self.dic[childName] = child_node
		parent_node.children.append(child_node)

	def death(self, name: str) -> None:
		self.dead[name] = True

	def getInheritanceOrder(self) -> List[str]:
		order_lst = []

		def recurse(root):
			if root.val not in self.dead:
				order_lst.append(root.val)
			for child in root.children:
				recurse(child)
		recurse(self.root)
		return order_lst


class P:

	def __init__(self, name):
		self.name = name
		self.child = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = P(kingName)
		self.d = {kingName: self.king}
		self.dead = set()

	def getnext(self, k):
		if k.name not in self.dead:
			yield k.name
		for c in k.child:
			yield from self.getnext(c)

	def birth(self, parentName: str, childName: str) -> None:
		child = P(childName)
		self.d[childName] = child
		self.d[parentName].child.append(child)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		return [*self.getnext(self.king)]


from collections import defaultdict

class Person:

	def __init__(self, name, parent):
		self.name = name
		self.is_alive = True
		self.parent = parent
		self.children = []

	def has_children(self):
		return True if len(self.children) > 0 else False

	def add_child(self, child):
		self.children.append(child)

class Order:

	def __init__(self):
		self.order = []
		self.names_set = set()

	def add(self, person):
		self.order.append(person)
		self.names_set.add(person.name)

	def not_in(self, persons):
		res = []
		for p in persons:
			if p.name not in self.names_set:
				res.append(p)
		return res

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.family = defaultdict(Person)
		self.king = Person(kingName, None)
		self.family[kingName] = self.king

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.family[parentName]
		new_child = Person(childName, parent)
		self.family[childName] = new_child
		self.family[parentName].add_child(new_child)

	def death(self, name: str) -> None:
		self.family[name].is_alive = False

	def getInheritanceOrder(self) -> 'List[str]':

		def successor(person, cur_order):
			children_not_in_order = cur_order.not_in(person.children)
			if not person.has_children() or not children_not_in_order:
				if person.parent is None:
					return None
				else:
					return successor(person.parent, cur_order)
			else:
				return children_not_in_order[0]
		order = Order()
		next_in_order = self.king
		while next_in_order:
			order.add(next_in_order)
			next_in_order = successor(next_in_order, order)
		res = []
		for p in order.order:
			if p.is_alive:
				res.append(p.name)
		return res


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.people = {kingName: []}
		self.dead = dict()
		self.kn = kingName

	def birth(self, parentName: str, childName: str) -> None:
		if self.people.get(parentName, 0) != 0:
			self.people[parentName].append(childName)
		else:
			self.people[parentName] = [childName]

	def death(self, name: str) -> None:
		self.dead[name] = 1

	def getInheritanceOrder(self) -> List[str]:
		res = []

		def dfs(curr, res):
			if self.dead.get(curr, 0) == 0:
				res.append(curr)
			if curr in list(self.people.keys()):
				for i in self.people[curr]:
					dfs(i, res)
		dfs(self.kn, res)
		return res


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.g = collections.defaultdict(list)
		self.rg = {}
		self.ROOT = kingName
		self.deathS = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.g[parentName].append(childName)
		self.rg[childName] = parentName

	def death(self, name: str) -> None:
		self.deathS.add(name)

	def getInheritanceOrder(self) -> List[str]:

		def succeed(x, currentOrder):
			if x:
				if len(self.g[x]) == 0 or all((i in currentOrder for i in self.g[x])):
					if x == self.ROOT:
						return None
					else:
						return succeed(self.rg[x], currentOrder)
				else:
					for i in self.g[x]:
						if i not in currentOrder:
							return i
			return None
		st = [self.ROOT]
		currentOrder = set()
		while st[-1] not in currentOrder:
			c = st[-1]
			currentOrder.add(c)
			nn = succeed(c, currentOrder)
			if nn:
				st.append(nn)
		res = [i for i in st if i not in self.deathS]
		return res


class Node:

	def __init__(self, name):
		self.name = name
		self.isdead = False
		self.children = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		p = Node('king')
		self.root = p
		self.dic = {kingName: p}

	def birth(self, parentName: str, childName: str) -> None:
		p = Node(childName)
		self.dic[childName] = p
		parent = self.dic[parentName]
		parent.children.append(p)

	def death(self, name: str) -> None:
		p = self.dic[name]
		p.isdead = True

	def getInheritanceOrder(self) -> List[str]:
		ans = []

		def dfs(n):
			if n and (not n.isdead):
				ans.append(n.name)
			for e in n.children:
				dfs(e)
		dfs(self.root)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = kingName
		self.inheritance = {kingName: []}
		self.dead = {}

	def birth(self, parentName: str, childName: str) -> None:
		if parentName in self.inheritance:
			self.inheritance[parentName].append(childName)
		self.inheritance[childName] = []

	def death(self, name: str) -> None:
		self.dead[name] = 1

	def getInheritanceOrder(self) -> List[str]:
		arr = []
		arr2 = []
		self.helper(self.root, arr)
		for person in arr:
			if person in self.dead:
				pass
			else:
				arr2.append(person)
		return arr2

	def helper(self, parent, arr):
		if len(self.inheritance[parent]) == 0:
			arr.append(parent)
			return
		arr.append(parent)
		for child in self.inheritance[parent]:
			self.helper(child, arr)


class Node:

	def __init__(self, name):
		self.name = name
		self.kids = []
		self.dead = False

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.head = Node(kingName)
		self.table = {}
		self.table[kingName] = self.head

	def birth(self, parentName: str, childName: str) -> None:
		self.table[childName] = Node(childName)
		self.table[parentName].kids.append(self.table[childName])

	def death(self, name: str) -> None:
		self.table[name].dead = True

	def getInheritanceOrder(self) -> List[str]:
		ans = []

		def helper(n):
			if not n.dead:
				ans.append(n.name)
			for k in n.kids:
				helper(k)
		helper(self.head)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.alive = {kingName: True}
		self.children = {kingName: []}
		self.order = [kingName]
		self.kingName = kingName
		self.placed = set([kingName])
		self.parent = {}

	def birth(self, parentName: str, childName: str) -> None:
		self.children[parentName].append(childName)
		self.children[childName] = []
		self.parent[childName] = parentName
		self.alive[childName] = True

	def death(self, name: str) -> None:
		self.alive[name] = False

	def getInheritanceOrder(self) -> List[str]:
		curr = self.kingName
		while True:
			curr = self.succ(curr)
			if curr is None:
				break
			self.order.append(curr)
			self.placed.add(curr)
		ret = [o for o in self.order if self.alive[o]]
		self.placed = set([self.kingName])
		self.order = [self.kingName]
		return ret

	def succ(self, x) -> str:
		if not self.children[x] or all([c in self.placed for c in self.children[x]]):
			if x == self.kingName:
				return None
			return self.succ(self.parent[x])
		for c in self.children[x]:
			if c not in self.placed:
				return c


class TreeNode:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.alive = True

class ThroneInheritance:
	mapping = {}

	def __init__(self, kingName: str):
		self.mapping[kingName] = TreeNode(kingName)
		self.kingName = kingName

	def birth(self, parentName: str, childName: str) -> None:
		c = TreeNode(childName)
		self.mapping[childName] = c
		self.mapping[parentName].children.append(c)

	def death(self, name: str) -> None:
		self.mapping[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		ret = []

		def dfs(node):
			if node.alive:
				ret.append(node.name)
			for c in node.children:
				dfs(c)
		dfs(self.mapping[self.kingName])
		return ret


from collections import defaultdict

class ListNode:

	def __init__(self, x, n=None):
		self.val = x
		self.next = n

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.head = ListNode(kingName)
		self.d = defaultdict(list)
		self.dead_people = {'king': 0}

	def birth(self, parentName: str, childName: str) -> None:
		self.d[parentName].append(childName)
		self.dead_people[childName] = 0

	def death(self, name: str) -> None:
		self.dead_people[name] = 1

	def df(self, name):
		l = []
		if self.dead_people[name] == 0:
			l.append(name)
		for childs in self.d[name]:
			l = l + self.df(childs)
		return l

	def getInheritanceOrder(self) -> List[str]:
		return self.df('king')


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.cache = {kingName: []}
		self.alive = {kingName: True}

	def birth(self, parentName: str, childName: str) -> None:
		self.alive[childName] = True
		if parentName not in self.cache:
			self.cache[parentName] = []
		self.cache[parentName].append(childName)

	def death(self, name: str) -> None:
		self.alive[name] = False

	def getInheritanceOrder(self) -> List[str]:
		order = []

		def DFS(parent):
			if self.alive[parent]:
				order.append(parent)
			if parent not in self.cache:
				return
			for child in self.cache[parent]:
				DFS(child)
		DFS(self.king)
		return order


class Node:

	def __init__(self, name, is_king, parent):
		self.name = name
		self.is_king = is_king
		self.parent = parent
		self.children = []
		self.is_dead = False

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName, True, None)
		self.nmap = {kingName: self.root}
		self.order_set = set()

	def successor(self, x):
		if not x.children or all((c in self.order_set for c in x.children)):
			if x.is_king:
				return None
			return self.successor(x.parent)
		else:
			for c in x.children:
				if c not in self.order_set:
					return c

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.nmap[parentName]
		child = Node(childName, False, parent)
		self.nmap[childName] = child
		parent.children.append(child)

	def death(self, name: str) -> None:
		self.nmap[name].is_dead = True

	def getInheritanceOrder(self) -> List[str]:
		res = [self.root]
		sc = self.successor(self.root)
		while sc:
			res.append(sc)
			self.order_set.add(sc)
			sc = self.successor(sc)
		self.order_set = set()
		return [n.name for n in res if not n.is_dead]


class Man:

	def __init__(self, name, father):
		self.name = name
		self.father = father
		self.children = []
		self.alive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.tree = Man(kingName, None)
		self.names = {kingName: self.tree}

	def birth(self, parentName: str, childName: str) -> None:
		father = self.names[parentName]
		man = Man(childName, father)
		father.children.append(man)
		self.names[childName] = man

	def death(self, name: str) -> None:
		self.names[name].alive = False

	def Succesor(self, man, curSet):
		if not man.children or all([c.name in curSet for c in man.children]):
			if man.father is None:
				return None
			else:
				return self.Succesor(man.father, curSet)
		else:
			for c in man.children:
				if c.name not in curSet:
					return c
		return None

	def getInheritanceOrder(self) -> List[str]:
		curSet = set()
		curList = []
		if self.tree and self.tree.alive:
			king = self.tree.name
			curList.append(king)
			curSet.add(king)
		succesor = self.Succesor(self.tree, curSet)
		while succesor:
			if succesor.alive:
				curList.append(succesor.name)
			curSet.add(succesor.name)
			succesor = self.Succesor(succesor, curSet)
		return curList


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.family = OrderedDict()
		self.family[kingName] = OrderedDict()
		self.parentChildrenDictMap = dict()
		self.parentChildrenDictMap[kingName] = self.family[kingName]
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		if parentName not in self.parentChildrenDictMap:
			raise Exception('No parent found')
		children = self.parentChildrenDictMap[parentName]
		if childName in children:
			raise Exception('Child already exists')
		children[childName] = OrderedDict()
		self.parentChildrenDictMap[childName] = children[childName]

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		ans = []

		def dfs(root):
			for (parent, children) in list(root.items()):
				if parent not in self.dead:
					ans.append(parent)
				dfs(root[parent])
		dfs(self.family)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.res = ['king']
		self.ex = {}
		self.par = {}
		self.child = {}

	def birth(self, pN: str, cN: str) -> None:
		self.child[cN] = pN
		if pN in self.par:
			self.par[pN].append(cN)
		else:
			self.par[pN] = deque([cN])

	def death(self, name: str) -> None:
		self.ex[name] = True

	def getInheritanceOrder(self) -> List[str]:
		final = []
		res = self.main()
		for i in res:
			if i not in self.ex:
				final.append(i)
		return final

	def main(self):
		cC = self.child.copy()
		cP = copy.deepcopy(self.par)
		res = ['king']
		curr = res[-1]
		while True:
			if curr in cP and len(cP[curr]) > 0:
				res.append(cP[curr][0])
				cP[curr].popleft()
				curr = res[-1]
			else:
				if curr not in cC:
					return res
				curr = cC[curr]
			if curr == 'king' and len(cP[curr]) == 0:
				return res


from collections import defaultdict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.family = defaultdict(list)
		self.dead = set()
		self.parent = dict()

	def birth(self, parentName: str, childName: str) -> None:
		self.family[parentName].append(childName)
		self.parent[childName] = parentName

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		order = [self.kingName]
		self.getInheritanceOrderFor(self.kingName, order)
		return [x for x in order if x not in self.dead]

	def getInheritanceOrderFor(self, name, order):
		for child in self.family[name]:
			order.append(child)
			self.getInheritanceOrderFor(child, order)


class TreeNode:

	def __init__(self, val):
		self.val = val
		self.children = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = TreeNode(kingName)
		self.mapping = collections.defaultdict()
		self.mapping[kingName] = self.root
		self.parent = collections.defaultdict()
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.mapping[parentName].children.append(childName)
		self.mapping[childName] = TreeNode(childName)
		self.parent[childName] = parentName

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		res = []

		def dfs(node):
			res.append(node.val)
			for child in node.children:
				dfs(self.mapping[child])
		dfs(self.root)
		return [name for name in res if name not in self.dead]


class Person:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.alive = True

	def dfs(self):
		res = []
		if self.alive:
			res.append(self.name)
		for child in self.children:
			res.extend(child.dfs())
		return res

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Person(kingName)
		self.mapping = {}
		self.mapping[kingName] = self.root

	def birth(self, parentName: str, childName: str) -> None:
		newOne = Person(childName)
		parent = self.mapping[parentName]
		self.mapping[childName] = newOne
		parent.children.append(newOne)

	def death(self, name: str) -> None:
		self.mapping[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		return self.root.dfs()


class Node:

	def __init__(self, name: str):
		self.name = name
		self.children = []
		self.alive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.lookup = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		p = self.lookup[parentName]
		child = Node(childName)
		p.children.append(child)
		self.lookup[childName] = child

	def death(self, name: str) -> None:
		person = self.lookup[name]
		person.alive = False

	def getInheritanceOrder(self) -> List[str]:
		ret = []

		def dfs(node: Node):
			if node.alive:
				ret.append(node.name)
			for child in node.children:
				dfs(child)
		dfs(self.root)
		return ret


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.childMap = dict([(kingName, [])])
		self.parentMap = dict([])
		self.grave = set([])

	def birth(self, parentName: str, childName: str) -> None:
		self.parentMap[childName] = parentName
		if parentName in self.childMap:
			self.childMap[parentName].append(childName)
		else:
			self.childMap[parentName] = [childName]

	def death(self, name: str) -> None:
		self.grave.add(name)

	def getInheritanceOrder(self) -> List[str]:
		curOrder = [self.kingName]
		curOrderSet = set(curOrder)
		n = self.successor(curOrder[-1], curOrder, curOrderSet)
		while n:
			curOrder.append(n)
			curOrderSet.add(n)
			n = self.successor(curOrder[-1], curOrder, curOrderSet)
		return [c for c in curOrder if c not in self.grave]

	def successor(self, x, curOrder, curOrderSet):
		if x in self.childMap:
			for c in self.childMap[x]:
				if c not in curOrderSet:
					return c
		if x == self.kingName:
			return None
		return self.successor(self.parentMap[x], curOrder, curOrderSet)


import collections

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.children = collections.defaultdict(list)
		self.dead = collections.defaultdict(bool)

	def birth(self, parentName: str, childName: str) -> None:
		self.children[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead[name] = True

	def getInheritanceOrder(self) -> List[str]:
		stack = [self.king]
		ans = []
		while stack:
			node = stack.pop()
			if not self.dead[node]:
				ans.append(node)
			for child in reversed(self.children[node]):
				stack.append(child)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.inherit = {}
		self.inherit[kingName] = []
		self.dead = {kingName: False}

	def birth(self, parentName: str, childName: str) -> None:
		self.inherit[childName] = []
		self.inherit[parentName].append(childName)
		self.dead[childName] = False
		return

	def death(self, name: str) -> None:
		self.dead[name] = True

	def getInheritanceOrder(self) -> List[str]:
		return self.dfs(self.kingName)

	def dfs(self, name: str) -> List[str]:
		ret = []
		if not self.dead[name]:
			ret.append(name)
		for val in self.inherit[name]:
			ret += self.dfs(val)
		return ret


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.k = kingName
		self.mp = defaultdict(list)
		self.d = set()

	def birth(self, p: str, c: str) -> None:
		self.mp[p].append(c)

	def death(self, name: str) -> None:
		self.d.add(name)

	def getInheritanceOrder(self) -> List[str]:
		ans = []
		stk = [self.k]
		while stk:
			x = stk.pop(0)
			if x not in self.d:
				ans.append(x)
			stk = self.mp[x] + stk
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.dead = {}
		self.mp = {}
		self.mp[kingName] = []

	def birth(self, parentName: str, childName: str) -> None:
		if parentName not in self.mp:
			self.mp[parentName] = []
		self.mp[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead[name] = True

	def getInheritanceOrder(self) -> List[str]:
		res = []

		def dfs(self, res, node):
			if node not in self.dead:
				res.append(node)
			if node not in self.mp:
				return
			for child in self.mp[node]:
				dfs(self, res, child)
		dfs(self, res, self.king)
		return res


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.family_tree = collections.defaultdict(list)
		self.king = kingName
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.family_tree[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:

		def dfs(name: str) -> None:
			if name not in self.dead:
				inheritance_order.append(name)
			for kid in self.family_tree[name]:
				dfs(kid)
		inheritance_order = []
		dfs(self.king)
		return inheritance_order


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = kingName
		self.dict = defaultdict(list)
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.dict[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		return self.dfs(self.root, [])

	def dfs(self, root, arr):
		if root not in self.dead:
			arr.append(root)
		if root in self.dict:
			for kid in self.dict[root]:
				self.dfs(kid, arr)
		return arr


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.G = collections.defaultdict(list)
		self.dead = set()
		self.king = kingName

	def birth(self, parentName: str, childName: str) -> None:
		self.G[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		ans = []

		def dfs(node, ans):
			if node not in self.dead:
				ans.append(node)
			for nei in self.G[node]:
				dfs(nei, ans)
		dfs(self.king, ans)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.family = {}
		self.family[kingName] = []
		self.dead = set([])

	def birth(self, parentName: str, childName: str) -> None:
		self.family[parentName].append(childName)
		self.family[childName] = []

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		order = []

		def dfs(name):
			if name not in self.dead:
				order.append(name)
			for child in self.family[name]:
				dfs(child)
		dfs(self.king)
		return order


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.graph = collections.defaultdict(lambda : [])
		self.dead = set()
		self.king = kingName

	def birth(self, parentName: str, childName: str) -> None:
		self.graph[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		ans = []

		def dfs(root):
			if not root:
				return
			if root not in self.dead:
				ans.append(root)
			for child in self.graph[root]:
				dfs(child)
		dfs(self.king)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king_name = kingName
		self.parents = collections.defaultdict(list)
		self.deads = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.parents[parentName].append(childName)

	def death(self, name: str) -> None:
		self.deads.add(name)

	def getInheritanceOrder(self) -> List[str]:
		res = []

		def dfs(name: str):
			if name not in self.deads:
				res.append(name)
			for child in self.parents[name]:
				dfs(child)
		dfs(self.king_name)
		return res


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.tree = collections.defaultdict(list)
		self.tree[kingName] = []
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.tree[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		res = []

		def dfs(name):
			res.append(name)
			for child in self.tree[name]:
				dfs(child)
		dfs(self.king)
		return [name for name in res if name not in self.dead]


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.data = {kingName: list()}
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.data[parentName].append(childName)
		self.data[childName] = list()

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		(out, seen) = ([], set())

		def _helper(person) -> None:
			if person not in seen:
				if person not in self.dead:
					out.append(person)
			for child in self.data[person]:
				_helper(child)
		_helper(self.king)
		return out


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.personDict = defaultdict(list)
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.personDict[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		self.ans = []
		self.dfs(self.kingName)
		return self.ans

	def dfs(self, name: str):
		if name not in self.dead:
			self.ans.append(name)
		for childName in self.personDict[name]:
			self.dfs(childName)


from collections import defaultdict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = kingName
		self.d = defaultdict(list)
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.d[parentName].append(childName)
		return

	def death(self, name: str) -> None:
		self.dead.add(name)
		return

	def getInheritanceOrder(self) -> List[str]:
		ans = []

		def p(root):
			nonlocal ans
			if root not in self.dead:
				ans.append(root)
			for i in self.d[root]:
				p(i)
		p(self.root)
		return ans


from collections import defaultdict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.family = defaultdict(list)
		self.king = kingName
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.family[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		self.ans = []
		self.dfs(self.king)
		return self.ans

	def dfs(self, root):
		if root not in self.dead:
			self.ans.append(root)
		for child in self.family[root]:
			self.dfs(child)


from collections import OrderedDict, defaultdict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.parent2son = {}
		self.parent2son[kingName] = OrderedDict()
		self.son2parent = {}
		self.deadset = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.son2parent[childName] = parentName
		if parentName not in self.parent2son:
			self.parent2son[parentName] = OrderedDict()
		self.parent2son[parentName][childName] = 0

	def death(self, name: str) -> None:
		self.deadset.add(name)

	def getInheritanceOrder(self) -> List[str]:
		order = []
		stack = [self.kingName]
		while stack:
			name = stack.pop()
			if name in self.parent2son:
				next = []
				for son in self.parent2son[name]:
					next.insert(0, son)
				stack = stack + next
			if name not in self.deadset:
				order.append(name)
		return order


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = kingName
		self.child_list = {self.root: []}
		self.death_dict = {}

	def birth(self, parentName: str, childName: str) -> None:
		self.child_list[parentName].append(childName)
		self.child_list[childName] = []

	def death(self, name: str) -> None:
		self.death_dict[name] = True

	def getInheritanceOrder(self) -> List[str]:
		answer_list = []

		def _dfs(cur_node):
			if cur_node not in self.death_dict:
				answer_list.append(cur_node)
			for child in self.child_list[cur_node]:
				_dfs(child)
		_dfs(self.root)
		return answer_list


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = kingName
		self.alive = {}
		self.alive[kingName] = 0
		self.edges = {self.root: []}

	def birth(self, parentName: str, childName: str) -> None:
		self.alive[childName] = self.alive[parentName] + 1
		if parentName in self.edges:
			self.edges[parentName].append(childName)
			if childName not in self.edges:
				self.edges[childName] = []
		else:
			if childName not in self.edges:
				self.edges[childName] = []
			self.edges[parentName] = [childName]

	def death(self, name: str) -> None:
		del self.alive[name]

	def getInheritanceOrder(self) -> List[str]:
		hierarchy = []

		def dfs(cur, parent=-1):
			nonlocal hierarchy
			if cur in self.alive:
				hierarchy.append(cur)
			for i in self.edges[cur]:
				if i != parent:
					dfs(i, cur)
		dfs(self.root)
		return hierarchy


class ThroneInheritance:

	def __init__(self, king: str):
		self.king = king
		self.g = defaultdict(list)
		self.dead = set()

	def birth(self, parent: str, child: str) -> None:
		self.g[parent].append(child)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		curOrder = []

		def recurse(u):
			curOrder.append(u)
			for v in self.g[u]:
				recurse(v)
		recurse(self.king)
		return [u for u in curOrder if u not in self.dead]


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.nameBook = {}
		self.nameBook[kingName] = (kingName, [])
		self.king = self.nameBook[kingName]
		self.deathBook = set()

	def birth(self, parentName: str, childName: str) -> None:
		if parentName in self.nameBook:
			self.nameBook[childName] = (childName, [])
			self.nameBook[parentName][1].append(self.nameBook[childName])

	def death(self, name: str) -> None:
		self.deathBook.add(name)

	def getInheritanceOrder(self) -> List[str]:
		InheritOrder = []
		stack = [self.king]
		while stack:
			(name, children) = stack.pop()
			if name not in self.deathBook:
				InheritOrder.append(name)
			stack.extend(children[::-1])
		return InheritOrder


class ThroneInheritance:
	from collections import deque

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.dic = {kingName: [1, []]}

	def birth(self, parentName: str, childName: str) -> None:
		self.dic[parentName][1].append(childName)
		self.dic[childName] = [1, []]

	def death(self, name: str) -> None:
		self.dic[name][0] = 0

	def getInheritanceOrder(self) -> List[str]:
		d = deque([self.kingName])
		ans = []
		while len(d) > 0:
			name = d.pop()
			if self.dic[name][0]:
				ans.append(name)
			listt = self.dic[name][1]
			for i in range(len(listt)):
				d.append(listt[-i - 1])
		return ans


class Person:

	def __init__(self, name):
		self.name = name
		self.alive = True
		self.children = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Person(kingName)
		self.name_person_map = {kingName: self.king}

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.name_person_map[parentName]
		child = Person(childName)
		parent.children.append(child)
		self.name_person_map[childName] = child

	def death(self, name: str) -> None:
		person = self.name_person_map[name]
		person.alive = False

	def getInheritanceOrder(self) -> List[str]:
		res = []
		self.preorder_dfs(self.king, res)
		return res

	def preorder_dfs(self, person, res):
		if person.alive:
			res.append(person.name)
		for child in person.children:
			self.preorder_dfs(child, res)


class Member:

	def __init__(self, name):
		self.name = name
		self.dead = False
		self.children = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.dummy = Member('')
		self.root = Member(kingName)
		self.dummy.children.append(self.root)
		self.member_table = {'king': self.root}

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.member_table[parentName]
		child = Member(childName)
		parent.children.append(child)
		self.member_table[childName] = child

	def death(self, name: str) -> None:
		self.member_table[name].dead = True

	def getInheritanceOrder(self) -> List[str]:

		def dfs(root, inheritance_order):
			for child in root.children:
				if not child.dead:
					inheritance_order.append(child.name)
				dfs(child, inheritance_order)
			return
		inheritance_order = []
		dfs(self.dummy, inheritance_order)
		return inheritance_order


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.alive = {kingName: True}
		self.children = {kingName: []}
		self.parent = {kingName: None}

	def birth(self, parentName: str, childName: str) -> None:
		self.alive[childName] = True
		self.children[childName] = []
		self.children[parentName].append(childName)
		self.parent[childName] = parentName

	def death(self, name: str) -> None:
		self.alive[name] = False

	def getInheritanceOrder(self) -> List[str]:
		ans = []
		if self.alive[self.king]:
			ans.append(self.king)
		cur = self.king
		index = [0]
		while cur:
			if len(self.children[cur]) > index[-1]:
				cur = self.children[cur][index[-1]]
				index[-1] += 1
				index.append(0)
				if self.alive[cur]:
					ans.append(cur)
			else:
				cur = self.parent[cur]
				index.pop()
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.tree = {kingName: [True, []]}

	def birth(self, parentName: str, childName: str) -> None:
		child = [True, []]
		self.tree[childName] = child
		self.tree[parentName][1].append(childName)

	def death(self, name: str) -> None:
		self.tree[name][0] = False

	def getInheritanceOrder(self) -> List[str]:
		result = []

		def dfs(root_name):
			result.append(root_name)
			if self.tree[root_name][1]:
				for child in self.tree[root_name][1]:
					dfs(child)
		dfs(self.king)
		return [x for x in result if self.tree[x][0]]


class Node(object):

	def __init__(self, name):
		self.name = name
		self.children = []
		self.isDead = False

	def addChild(self, child):
		self.children.append(child)

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.d = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		child = Node(childName)
		self.d[parentName].addChild(child)
		self.d[childName] = child

	def death(self, name: str) -> None:
		self.d[name].isDead = True

	def getInheritanceOrder(self) -> List[str]:
		order = []

		def dfs(root):
			if not root:
				return
			if not root.isDead:
				order.append(root.name)
			for c in root.children:
				dfs(c)
		dfs(self.root)
		return order


class Person:

	def __init__(self, name):
		self.children = []
		self.name = name
		self.isAlive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Person(kingName)
		self.persons = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		if parentName not in self.persons:
			return
		else:
			newChild = Person(childName)
			self.persons[parentName].children.append(newChild)
			self.persons[childName] = newChild

	def death(self, name: str) -> None:
		self.persons[name].isAlive = False

	def getInheritanceOrder(self) -> List[str]:
		ans = []

		def dfs(person):
			stack = [person]
			while len(stack) > 0:
				current = stack.pop()
				if current.isAlive:
					ans.append(current.name)
				for child in current.children[::-1]:
					stack.append(child)
		dfs(self.root)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.relation = {kingName: []}
		self.dead = {}

	def birth(self, parentName: str, childName: str) -> None:
		if parentName in self.relation:
			self.relation[parentName].append(childName)
		else:
			self.relation[parentName] = [childName]

	def death(self, name: str) -> None:
		self.dead[name] = True

	def getInheritanceOrder(self) -> List[str]:
		res = []
		self.dfs(self.kingName, res)
		return res

	def dfs(self, name, out):
		if name not in self.dead:
			out.append(name)
		if name not in self.relation:
			return
		for c in self.relation[name]:
			self.dfs(c, out)
		return


class Person:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.alive = True

	def birth(self, name):
		self.children.append(Person(name))
		return self.children[-1]

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Person(kingName)
		self.dic = {kingName: self.king}

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.dic[parentName]
		child = parent.birth(childName)
		self.dic[childName] = child

	def death(self, name: str) -> None:
		self.dic[name].alive = False

	def getInheritanceOrder(self) -> 'List[str]':
		res = []
		stack = [self.king]
		while stack:
			p = stack.pop()
			if p.alive:
				res.append(p.name)
			for child in p.children[::-1]:
				stack.append(child)
		return res


class Person:

	def __init__(self, name: str, parent):
		self.name = name
		self.parent = parent
		self.alive = True
		self.children = []

	def add_kid(self, kid):
		self.children.append(kid)

	def kill(self):
		self.alive = False

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Person(kingName, None)
		self.person_dict = {kingName: self.king}

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.person_dict[parentName]
		new_kid = Person(childName, parentName)
		self.person_dict[childName] = new_kid
		parent.add_kid(new_kid)

	def death(self, name: str) -> None:
		person = self.person_dict[name]
		person.kill()

	def getInheritanceOrder(self) -> List[str]:
		ans = []
		stack = [self.king]
		while stack:
			person = stack.pop()
			if person.alive:
				ans.append(person.name)
			if person.children:
				stack.extend(person.children[::-1])
		return ans


class Node:

	def __init__(self, name: str):
		self.name = name
		self.children = []
		self.is_dead = False

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = kingName
		self.nodes = {kingName: Node(kingName)}

	def birth(self, parentName: str, childName: str) -> None:
		child = Node(childName)
		self.nodes[parentName].children.append(child)
		self.nodes.update({childName: child})

	def death(self, name: str) -> None:
		self.nodes[name].is_dead = True

	def getInheritanceOrder(self) -> List[str]:
		result = []
		seq = [self.nodes[self.root]]
		while seq:
			one = seq.pop()
			if not one.is_dead:
				result.append(one.name)
			if one.children:
				seq.extend(one.children[::-1])
		return result


class ThroneInheritance:

	class Person:

		def __init__(self, name, parent=None):
			self.parent = parent
			self.name = name
			self.children = []
			self.isAlive = True

	def __init__(self, kingName: str):
		self.h = {kingName: self.Person(kingName)}
		self.cur_king = kingName

	def birth(self, parentName: str, childName: str) -> None:
		self.h[childName] = self.Person(childName, parentName)
		self.h[parentName].children.append(self.h[childName])

	def death(self, name: str) -> None:
		self.h[name].isAlive = False

	def getInheritanceOrder(self) -> List[str]:
		res = []
		stack = [self.h[self.cur_king]]
		while len(stack):
			node = stack[-1]
			stack.pop()
			if node.isAlive:
				res.append(node.name)
			for i in range(len(node.children)):
				stack.append(node.children[-1 - i])
		return res


import collections

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.mapping = collections.defaultdict(list)
		self.deads = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.mapping[parentName].append(childName)

	def death(self, name: str) -> None:
		self.deads.add(name)

	def getInheritanceOrder(self) -> List[str]:
		res = []
		self.get_order(res, self.kingName)
		return res

	def get_order(self, res, parent):
		if parent not in self.deads:
			res.append(parent)
		for child in self.mapping[parent]:
			self.get_order(res, child)


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.result = defaultdict(list)
		self.king = kingName
		self.dead = set()

	def successor(self, x):
		if x not in self.dead:
			self.order.append(x)
		for i in self.result[x]:
			self.successor(i)

	def birth(self, parentName: str, childName: str) -> None:
		self.result[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		self.order = []
		name = self.king
		self.successor(name)
		return self.order


class Member:

	def __init__(self, name):
		self.name = name
		self.alive = True
		self.nextChild = None
		self.nextSibling = None

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.members = {}
		self.king = Member(kingName)
		self.members[kingName] = self.king

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.members[parentName]
		child = Member(childName)
		self.members[childName] = child
		if parent.nextChild is None:
			parent.nextChild = child
			return
		member = parent.nextChild
		while member.nextSibling:
			member = member.nextSibling
		member.nextSibling = child

	def death(self, name: str) -> None:
		self.members[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		inheritanceOrder = []

		def traverseInOrder(member):
			if member is None:
				return
			if member.alive:
				inheritanceOrder.append(member.name)
			traverseInOrder(member.nextChild)
			traverseInOrder(member.nextSibling)
		traverseInOrder(self.king)
		return inheritanceOrder


class Node(object):

	def __init__(self):
		self.children = []
		self.name = ''
		self.dead = False

class ThroneInheritance:

	def __init__(self, kingName: str):
		self._root = Node()
		self._root.name = kingName
		self._locator = {kingName: self._root}

	def birth(self, parentName: str, childName: str) -> None:
		child = Node()
		child.name = childName
		self._locator[childName] = child
		self._locator[parentName].children.append(child)

	def death(self, name: str) -> None:
		self._locator[name].dead = True

	def getInheritanceOrder(self) -> List[str]:
		stack = []
		order = []
		current = self._root
		while True:
			if current:
				if not current.dead:
					order.append(current.name)
				stack.extend(current.children[::-1])
				current = None
			elif len(stack) > 0:
				(current, stack) = (stack[-1], stack[:-1])
			else:
				break
		return order


class Node:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.isAlive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Node(kingName)
		self.dict = {kingName: self.king}

	def birth(self, parentName: str, childName: str) -> None:
		new_node = Node(childName)
		self.dict[parentName].children.append(new_node)
		self.dict[childName] = new_node

	def death(self, name: str) -> None:
		self.dict[name].isAlive = False

	def getInheritanceOrder(self) -> List[str]:
		ordering = []

		def preOrder(node):
			if node.isAlive:
				ordering.append(node.name)
			for c in node.children:
				preOrder(c)
		preOrder(self.king)
		return ordering


class Node:

	def __init__(self, name):
		self.name = name
		self.alive = True
		self.childs = []

	def addChild(self, child):
		self.childs.append(child)

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Node(kingName)
		self.d = {kingName: self.king}

	def birth(self, parentName: str, childName: str) -> None:
		self.d[childName] = Node(childName)
		self.d[parentName].addChild(self.d[childName])

	def death(self, name: str) -> None:
		self.d[name].alive = False

	def getInheritanceOrder(self) -> List[str]:

		def dfs(node):
			ans = [node.name] * node.alive
			for x in node.childs:
				ans.extend(dfs(x))
			return ans
		return dfs(self.king)


class Node(object):

	def __init__(self, name, parent=None):
		self.name = name
		self.parent = parent
		self.children = []

	def addChild(self, child):
		self.children.append(child)

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.node = {kingName: self.root}
		self.deaths = set()

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.node[parentName]
		child = Node(childName, parent)
		parent.addChild(child)
		self.node[childName] = child

	def death(self, name: str) -> None:
		self.deaths.add(name)

	def getInheritanceOrder(self) -> List[str]:
		order = []

		def dfs(root):
			if not root:
				return
			if root.name not in self.deaths:
				order.append(root.name)
			for c in root.children:
				dfs(c)
		dfs(self.root)
		return order


class node:

	def __init__(self, name):
		self.name = name
		self.isdead = False
from collections import defaultdict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		n = node(kingName)
		self.nodes = {}
		self.nodes[kingName] = n
		self.child = defaultdict(list)
		self.child[n] = []

	def dfs(self, node):
		val = [node.name] if node.isdead == False else []
		for c in self.child[node]:
			c = self.nodes[c]
			n = self.dfs(c)
			val.extend(n)
		return val

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.nodes[parentName]
		child = node(childName)
		self.nodes[childName] = child
		self.child[parent].append(childName)

	def death(self, name: str) -> None:
		n = self.nodes[name]
		n.isdead = True

	def getInheritanceOrder(self) -> List[str]:
		n = self.nodes[self.kingName]
		return self.dfs(n)


class Node:

	def __init__(self, name):
		self.name = name
		self.children = []
		pass

	def give_birth_to(self, node):
		self.children.append(node)
		return

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.name_directory = dict()
		self.root = Node(kingName)
		self.name_directory[kingName] = self.root
		pass

	def birth(self, parentName: str, childName: str) -> None:
		child_node = Node(childName)
		self.name_directory[childName] = child_node
		parent_node = self.name_directory[parentName]
		parent_node.give_birth_to(child_node)
		pass

	def death(self, name: str) -> None:
		del self.name_directory[name]
		pass

	def getInheritanceOrder(self) -> List[str]:
		result = []

		def logic(node: Node, result: List[str]):
			if node == None:
				return
			if node.name in self.name_directory:
				result.append(node.name)
			for child in node.children:
				logic(child, result)
				pass
			return
		logic(self.root, result)
		return result


class ThroneInheritance:

	class FamilyMember:

		def __init__(self, name: str):
			self.name = name
			self.children = []
			self.is_alive = True

		def newChild(self, name: str):
			child = ThroneInheritance.FamilyMember(name)
			self.children.append(child)
			return child

		def kill(self):
			self.is_alive = False
	king = None
	family = {}
	inheritenceOrder = []

	def __init__(self, kingName: str):
		self.king = self.FamilyMember(kingName)
		self.family[kingName] = self.king

	def birth(self, parentName: str, childName: str) -> None:
		child = self.family[parentName].newChild(childName)
		self.family[childName] = child

	def death(self, name: str) -> None:
		self.family[name].kill()

	def buildInheritanceOrder(self, root: FamilyMember):
		if not root:
			return
		if root.is_alive:
			self.inheritenceOrder.append(root.name)
		for child in root.children:
			self.buildInheritanceOrder(child)
		return

	def getInheritanceOrder(self) -> List[str]:
		self.inheritenceOrder = []
		self.buildInheritanceOrder(self.king)
		return self.inheritenceOrder


from collections import OrderedDict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self._kingName = kingName
		self._family = {kingName: []}
		self._dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		self._family[parentName].append(childName)
		self._family[childName] = []

	def death(self, name: str) -> None:
		self._dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		order = []
		self._order(self._kingName, order)
		return order

	def _order(self, name, order):
		if name not in self._dead:
			order.append(name)
		for child in self._family[name]:
			self._order(child, order)


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingname = kingName
		self.dead = set()
		self.m = collections.defaultdict(list)
		self.m[kingName] = []

	def birth(self, parentName: str, childName: str) -> None:
		self.m[parentName].append(childName)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getorderhelper(self, name, order):
		if name not in self.dead:
			order.append(name)
		for n in self.m[name]:
			self.getorderhelper(n, order)

	def getInheritanceOrder(self) -> List[str]:
		order = []
		self.getorderhelper(self.kingname, order)
		return order


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.tree = {kingName: [True, []]}

	def birth(self, parentName: str, childName: str) -> None:
		self.tree[parentName][1].append(childName)
		self.tree[childName] = [True, []]

	def death(self, name: str) -> None:
		self.tree[name][0] = False

	def dfs(self, name):
		if self.tree[name][0]:
			yield name
		for child in self.tree[name][1]:
			yield from self.dfs(child)

	def getInheritanceOrder(self) -> List[str]:
		return list(self.dfs(self.king))


class ThroneInheritance:

	class Person:

		def __init__(self, name):
			self.name = name
			self.children = list()
			self.is_alive = True

	def __init__(self, kingName: str):
		self.root = ThroneInheritance.Person(kingName)
		self.tracker = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		if parentName not in self.tracker:
			return
		self.tracker[parentName].children.append(ThroneInheritance.Person(childName))
		self.tracker[childName] = self.tracker[parentName].children[-1]

	def death(self, name: str) -> None:
		self.tracker[name].is_alive = False

	def getInheritanceOrder(self) -> List[str]:
		res = list()

		def recursion(node):
			if node.is_alive:
				res.append(node.name)
			for child in node.children:
				recursion(child)
		recursion(self.root)
		return res


class people:

	def __init__(self, name, dead=False, child=None):
		self.name = name
		self.dead = dead
		self.child = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		king = people(kingName)
		self.hash = {kingName: king}
		self.king = king

	def birth(self, parentName: str, childName: str) -> None:
		pp = people(childName)
		self.hash[parentName].child.append(pp)
		self.hash[childName] = pp

	def death(self, name: str) -> None:
		self.hash[name].dead = True

	def getInheritanceOrder(self):
		self.res = []

		def dfs(pp):
			print(pp.name)
			if not pp.dead:
				self.res.append(pp.name)
			for v in pp.child:
				dfs(v)
		dfs(self.king)
		return self.res


class Person:

	def __init__(self, name):
		self.name = name
		self.alive = True
		self.children = []

	def preOrder(self, output):
		if self.alive:
			output.append(self.name)
		for child in self.children:
			child.preOrder(output)

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Person(kingName)
		self.people = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		child = Person(childName)
		self.people[parentName].children.append(child)
		self.people[childName] = child

	def death(self, name: str) -> None:
		self.people[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		ret = []
		self.root.preOrder(ret)
		return ret


class King:

	def __init__(self, name):
		self.name = name
		self.children = dict()

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = King(kingName)
		self.inheritTree = collections.defaultdict(King)
		self.inheritTree[kingName] = self.king
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		tree = self.inheritTree
		parentNode = tree[parentName]
		childNode = King(childName)
		parentNode.children[childName] = childNode
		tree[childName] = childNode

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		tree = self.inheritTree
		res = []

		def inorder(king, res):
			if king not in self.dead:
				res.append(king)
			child = tree[king]
			for c in child.children:
				inorder(c, res)
		king = self.king
		inorder(king.name, res)
		return res


class Node:

	def __init__(self, val, childs=None):
		(self.val, self.childs) = (val, childs if childs else [])

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.name2node = {kingName: self.root}
		self.dead = set()

	def birth(self, parentName: str, childName: str) -> None:
		par = self.name2node[parentName]
		node = Node(childName)
		par.childs.append(node)
		self.name2node[childName] = node

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:

		def helper(r):
			if r.val not in self.dead:
				ans.append(r.val)
			for child in r.childs:
				helper(child)
		ans = []
		helper(self.root)
		return ans


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.pc = defaultdict(list)
		self.deathset = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.pc[parentName].append(childName)

	def death(self, name: str) -> None:
		self.deathset.add(name)

	def getInheritanceOrder(self) -> List[str]:
		ans = []
		self.recur(self.king, ans)
		return ans

	def recur(self, name: str, ans: List[str]) -> None:
		if name not in self.deathset:
			ans.append(name)
		for child in self.pc[name]:
			self.recur(child, ans)


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.inh = {kingName: (None, True, [])}

	def birth(self, parentName: str, childName: str) -> None:
		self.inh[parentName][-1].append(childName)
		self.inh[childName] = (parentName, True, [])

	def death(self, name: str) -> None:
		(p, _, ch) = self.inh[name]
		self.inh[name] = (p, False, ch)

	def getInheritanceOrder(self) -> List[str]:
		order = [self.king]
		s = set(order)

		def fs(x):
			(p, a, ch) = self.inh[x]
			for c in ch:
				order.append(c)
				s.add(c)
				fs(c)
		fs(self.king)
		return [o for o in order if self.inh[o][1]]


from collections import OrderedDict

class Person:

	def __init__(self, name):
		self.name = name
		self.alive = True
		self.children = []
		self.parent = None
		self._successor = None

	@property
	def successor():
		if not self.children:
			return self.parent
		else:
			return self.children[0]

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = Person(kingName)
		self.people = {kingName: self.king}

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.people[parentName]
		child = Person(childName)
		child.parent = parent
		self.people[childName] = child
		parent.children.append(child)

	def death(self, name: str) -> None:
		person = self.people[name]
		person.alive = False

	def successor(self, x, curOrder):
		curNames = set(curOrder)
		if not x.children or set([c.name for c in x.children]) <= curNames:
			if x.name == self.king.name:
				return None
			else:
				return self.successor(x.parent, curOrder)
		else:
			for c in x.children:
				if c.name not in curNames:
					return c.name

	def inorder(self, t):
		res = [t.name]
		for c in t.children:
			res += self.inorder(c)
		return res

	def getInheritanceOrder(self) -> List[str]:
		return [name for name in self.inorder(self.king) if self.people[name].alive]

	def a():
		curOrder = [self.king.name]
		x = self.king
		while len(curOrder) < len(self.people):
			newsuc = self.successor(x, curOrder)
			x = self.people[newsuc]
			curOrder.append(newsuc)
		return [name for name in curOrder if self.people[name].alive]


class Node:

	def __init__(self):
		self.name = None
		self.children = []
		self.parent = None
		self.isDead = False

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node()
		self.root.name = kingName
		self.lookup = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		curr = Node()
		curr.name = childName
		curr.parent = parentName
		self.lookup[parentName].children.append(curr)
		self.lookup[childName] = curr

	def death(self, name: str) -> None:
		self.lookup[name].isDead = True

	def getInheritanceOrder(self) -> List[str]:
		return self.dfs(self.root)

	def dfs(self, node):
		if node.isDead:
			result = []
		else:
			result = [node.name]
		for c in node.children:
			result += self.dfs(c)
		return result


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = kingName
		self.deathed = set()
		self.hmap = {kingName: []}

	def birth(self, parentName: str, childName: str) -> None:
		self.hmap[parentName].append(childName)
		self.hmap[childName] = []

	def death(self, name: str) -> None:
		self.deathed.add(name)

	def getInheritanceOrder(self) -> List[str]:

		def dfs(node):
			for st in self.hmap[node]:
				if st not in self.deathed:
					ans.append(st)
				dfs(st)
		ans = [self.root] if self.root not in self.deathed else []
		dfs(self.root)
		return ans


from collections import defaultdict as dict

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.graph = dict(list)
		self.visited = {}
		self.death_set = set()
		self.kingName = kingName

	def birth(self, parentName: str, childName: str) -> None:
		self.graph[parentName].append(childName)
		if parentName not in list(self.visited.keys()):
			self.visited[parentName] = False
		if childName not in list(self.visited.keys()):
			self.visited[childName] = False

	def death(self, name: str) -> None:
		self.death_set.add(name)

	def getInheritanceOrder(self) -> List[str]:
		stack = []
		u = self.kingName
		self.get_dfs(u, self.visited, self.graph, stack)
		self.reset_visit(self.visited)
		return stack

	def get_dfs(self, u, visited, graph, stack):
		visited[u] = True
		if u not in self.death_set:
			stack.append(u)
		for v in graph[u]:
			if visited[v] == False:
				self.get_dfs(v, visited, graph, stack)

	def reset_visit(self, visited):
		for key in list(visited.keys()):
			visited[key] = False


class Node:

	def __init__(self, name):
		self.name = name
		self.alive = True
		self.children = deque()

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.map = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		p = self.map[parentName]
		q = Node(childName)
		p.children.appendleft(q)
		self.map[childName] = q

	def death(self, name: str) -> None:
		self.map[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		ret = []
		s = [self.root]
		while s:
			p = s.pop()
			if p.alive:
				ret.append(p.name)
			s.extend(p.children)
		return ret


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.lineageTree = [kingName, []]
		self.lineageLocs = {kingName: self.lineageTree}
		self.deaths = set([])

	def birth(self, parentName: str, childName: str) -> None:
		parentLoc = self.lineageLocs[parentName]
		parentLoc[1].append([childName, []])
		self.lineageLocs[childName] = parentLoc[1][-1]

	def death(self, name: str) -> None:
		self.deaths.add(name)

	def getInheritanceOrder(self) -> List[str]:

		def doit(node, deaths):
			if node == []:
				return []
			res = []
			if node[0] not in deaths:
				res.append(node[0])
			for childNode in node[1]:
				res = res + doit(childNode, deaths)
			return res
		return doit(self.lineageTree, self.deaths)


class node:

	def __init__(self, name):
		self.name = name
		self.children = []
		self.isdead = False

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = node(kingName)
		self.m = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		p = self.m[parentName]
		c = node(childName)
		p.children.append(c)
		self.m[childName] = c

	def death(self, name: str) -> None:
		self.m[name].isdead = True

	def getInheritanceOrder(self) -> List[str]:
		cur = self.root
		res = []

		def helper(cur):
			if not cur.isdead:
				res.append(cur.name)
			for c in cur.children:
				helper(c)
		helper(cur)
		return res


class TreeNode:

	def __init__(self, personName):
		self.name = personName
		self.children = []
		self.parent = None

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = TreeNode(kingName)
		self.dead = set()
		self.treeMap = {}
		self.treeMap[kingName] = self.king
		self.ret = []

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.treeMap[parentName]
		child = TreeNode(childName)
		self.treeMap[childName] = child
		child.parent = parent
		parent.children.append(child)

	def death(self, name: str) -> None:
		self.dead.add(name)

	def getInheritanceOrder(self) -> List[str]:
		self.ret = []

		def helper(node):
			if node.name not in self.dead:
				self.ret.append(node.name)
			for (i, child) in enumerate(node.children):
				helper(node.children[i])
		helper(self.king)
		return self.ret


class node:

	def __init__(self, name):
		self.data = name
		self.children = []

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = node(kingName)
		self.dic = {}
		self.dic[kingName] = self.root
		self.dead = {}

	def birth(self, parentName: str, childName: str) -> None:
		curr = self.dic[parentName]
		new = node(childName)
		curr.children.append(new)
		self.dic[childName] = new

	def death(self, name: str) -> None:
		self.dead[name] = True

	def getInheritanceOrder(self) -> List[str]:

		def dfs(node, ans):
			if node.data not in self.dead:
				ans.append(node.data)
			for child in node.children:
				dfs(child, ans)
		ans = []
		dfs(self.root, ans)
		return ans


class Node:

	def __init__(self, val):
		self.val = val
		self.child = []
		self.alive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.root = Node(kingName)
		self.dic = {kingName: self.root}

	def birth(self, parentName: str, childName: str) -> None:
		child = Node(childName)
		self.dic[parentName].child.append(child)
		self.dic[childName] = child

	def death(self, name: str) -> None:
		self.dic[name].alive = False

	def getInheritanceOrder(self) -> List[str]:
		res = []

		def dfs(node):
			if not node:
				return
			if node.alive:
				res.append(node.val)
			for n in node.child:
				dfs(n)
		dfs(self.root)
		return res


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.g = defaultdict(list)
		self.king_name = kingName
		self.g[kingName] = list()
		self.parent = {}
		self.d = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.g[parentName].append(childName)
		self.parent[childName] = parentName

	def death(self, name: str) -> None:
		self.d.add(name)
		return None

	def getInheritanceOrder(self) -> List[str]:

		def successor(node, order, order_set):
			if not self.g[node] or set(self.g[node]) & order_set == set(self.g[node]):
				if node == self.king_name:
					return
				else:
					successor(self.parent[node], order, order_set)
			else:
				for n in self.g[node]:
					if n not in order_set:
						order.append(n)
						order_set.add(n)
						return
		order = [self.king_name]
		order_set = set(order)
		added = True
		while added:
			prev_size = len(order)
			successor(order[-1], order, order_set)
			added = prev_size < len(order)
		return [o for o in order if o not in self.d]


class Member:

	def __init__(self, name):
		self.name = name
		self.children = list()
		self.isAlive = True

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingdom = dict()
		self.king = Member(kingName)
		self.kingdom[kingName] = self.king

	def birth(self, parentName: str, childName: str) -> None:
		parent = self.kingdom[parentName]
		child = Member(childName)
		self.kingdom[childName] = child
		parent.children.append(child)

	def death(self, name: str) -> None:
		member = self.kingdom[name]
		member.isAlive = False

	def getInheritanceOrder(self) -> List[str]:
		order = []
		stack = [self.kingdom[self.king.name]]
		while stack:
			member = stack.pop()
			if member.isAlive:
				order.append(member.name)
			for i in range(len(member.children) - 1, -1, -1):
				stack.append(member.children[i])
		return order


import collections

class Node:

	def __init__(self, name):
		self.name = name
		self.alive = True
		self.children = []

	def addChild(self, node):
		self.children.append(node)

	def setDeath(self):
		self.alive = False

	def getName(self):
		return self.name

	def getChildren(self):
		return self.children

	def isAlive(self):
		return self.alive

class ThroneInheritance:

	def __init__(self, kingName: str):
		self.kingName = kingName
		self.name_node = {kingName: Node(kingName)}

	def birth(self, parentName: str, childName: str) -> None:
		child = Node(childName)
		parent = self.name_node[parentName]
		parent.addChild(child)
		self.name_node[childName] = child

	def death(self, name: str) -> None:
		person = self.name_node[name]
		person.setDeath()

	def getInheritanceOrder(self) -> List[str]:

		def dfs(node):
			if node:
				name = node.getName()
				if node.isAlive():
					order.append(name)
				children = node.getChildren()
				for child in children:
					dfs(child)
		node = self.name_node[self.kingName]
		order = []
		dfs(node)
		return order


class ThroneInheritance:

	def __init__(self, kingName: str):
		self.king = kingName
		self.family = defaultdict(list)
		self.deadName = set()

	def birth(self, parentName: str, childName: str) -> None:
		self.family[parentName].append(childName)

	def death(self, name: str) -> None:
		self.deadName.add(name)

	def getInheritanceOrder(self) -> List[str]:
		res = []

		def dfs(name):
			if name not in self.deadName:
				res.append(name)
			for n in self.family[name]:
				dfs(n)
		dfs(self.king)
		return res