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.

Difficulty: interview

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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]:
        # dfs
        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)


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

# inheritance -> king is first member
# recursive function Successor(x, curOrder) which gives person x and the inheritance order so far, returns who should be the nextg person after x in the order of inheritance.


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.kn = kingName
        # get_child[parent] = ([child in order], start_index)
        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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


#   多叉树--前序遍历
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
        
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class ThroneInheritance:
    class Person:
        def __init__(self,name):
            self.name = name
            self.alive = True
    def __init__(self, kingName: str):
        self.tree = {}
        self.king = self.Person(kingName)
        self.name_map = {kingName:self.king}
        self.tree[self.king] = []
    
    def printTree(self):
        for p,v in self.tree.items():
            print(p.name + \" : \" ,end = \" \")
            for c in v:
                print(c.name, end = \"  \")
            print()
    
    def birth(self, parentName: str, childName: str) -> None:
        child = self.Person(childName)
        self.tree[self.name_map[parentName]].append(child)
        self.name_map[childName] = child
        self.tree[child] = []
        #self.printTree()
        

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

    def getInheritanceOrder(self) -> List[str]:
        inheritance = []
        def rec(person):
            if person.alive:
                inheritance.append(person.name)
            for child in self.tree[person]:
                rec(child)
        rec(self.king)
        return inheritance
                
            
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


#junge

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.parent = None
        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)
        #child.parent = parentName
        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)


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


import collections


class ThroneInheritance(object):

    def __init__(self, kingName):
        \"\"\"
        :type kingName: str
        \"\"\"
        self.__king = kingName
        self.__family_tree = collections.defaultdict(list)
        self.__dead = set()


    def birth(self, parentName, childName):
        \"\"\"
        :type parentName: str
        :type childName: str
        :rtype: None
        \"\"\"
        self.__family_tree[parentName].append(childName)


    def death(self, name):
        \"\"\"
        :type name: str
        :rtype: None
        \"\"\"
        self.__dead.add(name)


    def getInheritanceOrder(self):
        \"\"\"
        :rtype: List[str]
        \"\"\"
        result = []
        stk = [self.__king]
        while stk:  # preorder traversal
            node = stk.pop()
            if node not in self.__dead:
                result.append(node)
            if node not in self.__family_tree:
                continue
            for child in reversed(self.__family_tree[node]):
                stk.append(child)
        return result

        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.G = collections.defaultdict(list)
        self.dead = set()
        self.king = kingName
        self.parent = dict()
    def birth(self, parentName: str, childName: str) -> None:
        self.G[parentName].append(childName)
        self.parent[childName] = parentName
    def death(self, name: str) -> None:
        self.dead.add(name)

    def getInheritanceOrder(self) -> List[str]:
        toVisit = collections.defaultdict(int)
        visited = set()
        ans = []
        def dfs(node, ans):
            if node not in self.dead and node not in visited:
                visited.add(node)
                ans.append(node)
            if toVisit[node] == len(self.G[node]):
                if node == self.king:
                    return 
                else:
                    return dfs(self.parent[node], ans)
            else:
                toVisit[node] +=1
                dfs(self.G[node][toVisit[node]-1], ans)
        dfs(self.king, ans)
        return ans
        
        \"\"\"         
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
\"\"\"
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

class ThroneInheritance:
    
    allNames={}

    def __init__(self, kingName: str):
        # order=[kingName]
        # familyTree=Tree(kingName)
        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



# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


\"\"\"
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
\"\"\"

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.children = collections.defaultdict(list)
        self.dead = set()
        self.king = kingName
        
    def birth(self, parentName: str, childName: str) -> None:
        self.children[parentName].append(childName)

    def death(self, name: str) -> None:
        self.dead.add(name)
    
    def getInheritanceOrder(self) -> List[str]:
        res = []
        visited = set()
        self.dfs(self.king, res, visited)
        if self.king not in self.dead:
            return [self.king] + res
        return res
        
    def dfs(self, node, res, visited):
        for nxt in self.children[node]:
            if nxt not in visited:
                visited.add(node)
                if nxt not in self.dead:
                    res.append(nxt)
                self.dfs(nxt, res, visited)
            
                
        
        
            
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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
    
    
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Tree: 
    def __init__(self, name, state = \"live\"): 
        self.children = []
        self.name = name
        self.state = state
   
    
class ThroneInheritance:
    
    king = \"\"
    root = None
    order = {}
    def __init__(self, kingName: str):
        self.king = kingName
        self.root = Tree(kingName)
        self.order[kingName] = self.root

    def birth(self, parentName: str, childName: str) -> None:
        node = Tree(childName)
        
        if parentName == self.king: 
            self.root.children.append(node)
        else: 
            self.order[parentName].children.append(node)
            
        self.order[childName] = node

    def death(self, name: str) -> None:
        self.order[name].state = \"dead\"

    def getInheritanceOrder(self) -> List[str]:
        return self.preorder(self.root)
            
    def preorder(self, root): 
        if root is None: return []
        
        sk, out = [root, ], []
    
        while sk: 
            root = sk.pop()
            if root.state == \"live\": 
                out.append(root.name)
            sk.extend(root.children[::-1])
            
        return out

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

class Tree:
    def __init__(self, name):
        self.val = name
        self.descents = []
        
        
class ThroneInheritance:
    
    def __init__(self, kingName: str):
        self.dic={}  # name:实体
        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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()




class Family:
    def __init__(self, parent):
        self.parent = parent
        self.children = []
    
    def __repr(self):
        return f\"parent: {self.parent}, children: {self.children}\"
        
class ThroneInheritance:

    def __init__(self, kingName: str):
        self.isdead = set()
        self.hierarchy = defaultdict(Family)
        self.hierarchy[kingName] = Family(None)

    def birth(self, parentName: str, childName: str) -> None:
        self.hierarchy[parentName].children.append(childName)
        self.hierarchy[childName] = Family(parentName)
        
    def death(self, name: str) -> None:
        self.isdead.add(name)

    def getInheritanceOrder(self) -> List[str]:            
        # def successor(x, curorder):
        #     if not self.hierarchy[x].children or all(child in curorder for child in self.hierarchy[x].children):
        #         if x == 'king': return None
        #         else: return successor(self.hierarchy[x].parent, curorder)
        #     else:
        #         for child in self.hierarchy[x].children:
        #             if child not in curorder:
        #                 return child
        # curorder = ['king']
        # curorder_set = ('king')
        # nxt = successor('king', curorder_set)
        # while nxt:
        #     curorder.append(nxt)
        #     nxt = successor(curorder[-1], curorder)
        
        i = 0
        curorderq, curorder = collections.deque(['king']), []
        while curorderq:
            curorder.append(curorderq.popleft())
            if self.hierarchy[curorder[-1]].children:
                for achild in self.hierarchy[curorder[-1]].children[::-1]:
                    curorderq.appendleft(achild)
        return [a for a in curorder if not a in self.isdead]


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 getInheritanceOrder(self) -> List[str]:
        result = []
        def dfs(node, result):
            if node not in self.deaths:
                result.append(node)
            children = self.graph[node]
            for child in children:
                dfs(child, result)
        
        dfs(self.root, result)
        return result


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
    # @lru_cache(None)
    def Successor(self, x):
        # print(self.map, self.parent)
        # print(x, self.curOrder)
        # self.curOrder += [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: #all of x's children are in curOrder:
            if x == self.king:
                return None
            else: 
                return self.Successor(self.parent[x])
        else:
            # return x's oldest child who's not in curOrder
            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]


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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:
        # del self.family[name]
        self.dead.add(name)
        # if name == self.king:
            # self.king = self.getInheritanceOrder()[1]
        # self.size -= 1
        
    def getInheritanceOrder(self) -> List[str]:
        ans = [self.king]
        pool = set(self.king)
        def sccesssor(x, curOrder):
            # print(x, f\"{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]:
                    # print(name)
                    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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
        

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
        #######################################################
        # optimization 1: remember last_child for chain in O(1)  
        #######################################################
        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
        # first child
        if children == None:
            parent.first_child = Person(childName, parentName)
            self.person_map[childName] = parent.first_child
            parent.last_child = parent.first_child
            #print('1 children:', parent.children.name, 'parent:', parent.children.p_name)
            #print('1 self.person_map=', self.person_map)
            #print('------')
        else:
            # add after last child
            parent.last_child.sibling = Person(childName, parentName)
            parent.last_child = parent.last_child.sibling
            self.person_map[childName] = parent.last_child
            #print('3 children:', children.name, 'parent:', children.p_name)
            #print('3 children.sibling:', children.sibling.name, 'parent:', children.sibling.p_name)
            #print('3 self.person_map=', self.person_map)
            #print('------')
            
        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]:
        # 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
        def successor(person_map, x, curOrder, curOrder_pos):
            p = person_map[x]
            # check if all p's children are in curOrder
            c = p.first_child
            o_c = None
            while c:
                #####################################
                # optimization 2: O(1) search in dict  
                #####################################
                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]]
            ###################################################################
            # optimization 3: only recalculate inheritence from parent impacted  
            ###################################################################
            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
            

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
                


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.died = set()
        self.hmap = defaultdict(lambda : list())
        

    def birth(self, parentName: str, childName: str) -> None:
        self.hmap[parentName].append(childName)
        
    def death(self, name: str) -> None:
        self.died.add(name)
        
    def getInheritanceOrder(self) -> List[str]:
        res = list()
        q = [\"king\"]
        
        while q:
            name = q.pop()
            
            if name not in self.died:
                res.append(name)
                
            for child in self.hmap[name][::-1]:
                q.append(child)
                
        return res
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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]
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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 getInheritanceOrder(self) -> List[str]:
        self.ans = []
        self.dfs(self.king)
        return self.ans
    
    def dfs(self, cur):
        if cur not in self.dead:
            self.ans.append(cur)
        for child in self.nation.get(cur,()):
            self.dfs(child)


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
#[\"king\", \"andy\", \"matthew\", \"bob\", \"alex\", \"asha\", \"catherine\"]
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

# [\"ThroneInheritance\",\"birth\",\"birth\",\"birth\",\"getInheritanceOrder\"]
# [[\"king\"],[\"king\",\"andy\"],[\"king\",\"bob\"],[\"andy\",\"matthew\"],[null]]


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)
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
            
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class ThroneInheritance:

    def __init__(self, kingName: str):
        dummy = TreeNode('', None)
        self.root = dummy
        self.lookup = {}
        
        self._addNode(kingName, dummy)

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

    def death(self, name: str) -> None:
        if name not in self.lookup:
            return
        
        node = self.lookup[name]
        #no children
        if node.firstChild.next.name == '':
            node.prev.next = node.next
            node.next.prev = node.prev
        else:
            firstChild = node.firstChild.next
            lastChild = node.lastChild.prev
            node.prev.next = firstChild
            firstChild.prev = node.prev
            node.next.prev = lastChild
            lastChild.next = node.next
            
        del node        

    def getInheritanceOrder(self) -> List[str]:
        res = []
        self._dfs(self.root, res)
        return res
        
    def _dfs(self, cur, res):
        if not cur:
            return
        
        if cur.name != '':
            res.append(cur.name)
            
        child = cur.firstChild
        while child:
            self._dfs(child, res)
            child = child.next
        
    def _addNode(self, name, parentNode):
        node = TreeNode(name, parentNode)
        self.lookup[name] = node
        
        prev = parentNode.lastChild.prev
        nxt = parentNode.lastChild
        node.prev = prev
        node.next = nxt
        prev.next = node
        nxt.prev = node
        
    def _print(self, name, node):
        print(name)
        while node:
            print(node.name + \"+\")
            node = node.next
        
class TreeNode:
    def __init__(self, name, parent):
        self.name = name
        self.parent = parent
        self.next = None
        self.prev = None
        self.firstChild = DummyNode()
        self.lastChild = DummyNode()
        
        self.firstChild.next = self.lastChild
        self.lastChild.prev = self.firstChild
        
class DummyNode:
    def __init__(self):
        self.name = ''
        self.next = None
        self.prev = None
        self.firstChild = None
        self.lastChild = None

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

class ThroneInheritance:
    import collections
    
    def __init__(self, kingName: str):
        self.king_name = kingName
        self.dead = set([]) # names of dead people
        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]


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


import copy
class ThroneInheritance:

    def __init__(self, kingName: str):
        self.parent = collections.defaultdict(list) # child : parent
        self.children = collections.defaultdict(list) # parent: children
        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
        #print(self.parent, self.children)
        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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)
        #print(self.parent)

    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
            
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]:
        # dfs with living members
        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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
        
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Node:
    def __init__(self, name):
        self.name = name
        self.prev = None
        self.next = None
        
class ThroneInheritance:

    def __init__(self, kingName: str):
        self.deaths = set()
        self.deaths.add(\"\")
        self.nameToNode = {}
        self.head = Node(\"\")
        self.tail = Node(\"\")
        self.kingName = kingName
        
        king = Node(kingName)
        self.head.next = king
        king.next = self.tail
        self.tail.prev = king
        king.prev = self.head
        
        self.nameToNode[kingName] = {\"node\": king, \"children\": [], \"parent\": None}
        
    def birth(self, parentName: str, childName: str) -> None:
        parent = self.nameToNode[parentName]
        prev_node = parent[\"node\"]
        if parent[\"children\"]:
            prev_node = parent[\"children\"][-1]
            while self.nameToNode[prev_node.name][\"children\"]:
                prev_node = self.nameToNode[prev_node.name][\"children\"][-1]
        
        c_node = Node(childName)
        parent[\"children\"].append(c_node)
        self.nameToNode[childName] = {\"node\":c_node, \"children\":[], \"parent\": parent[\"node\"]}
        
        post_node = prev_node.next
        prev_node.next = c_node
        c_node.next = post_node
        post_node.prev = c_node
        c_node.prev = prev_node
        

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

    def getInheritanceOrder(self) -> List[str]:
        node = self.nameToNode[self.kingName][\"node\"]
        res = []
        while node:
            if node.name not in self.deaths:
                res.append(node.name)
            node = node.next
        return res
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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]
                
                
        
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Person:
    def __init__(self, name, parent=None, children=[], isdead = False):
        self.name = name
        self.children = children
        self.parent = parent
        self.isdead = False

        

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.kingName = kingName
        kingNode = Person(kingName, parent=\"kingfather\",children=[],isdead =False)
        self.Order = {kingName:kingNode}

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

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

    def getInheritanceOrder(self) -> List[str]:
        children_remain = {}
        for key,val in self.Order.items():
            
            children_remain[key] = len(self.Order[key].children)

        
        curOrder = []
        visited = {}

        self.Successor(self.kingName,curOrder,visited,children_remain)
        return curOrder

        
    def Successor(self,curName,curOrder,visited,children_remain):
        
        
        # print(self.Order[curName].children)
        # print(children_remain[curName])
        if self.Order[curName].isdead == False and curName not in visited:
            curOrder.append(curName)
            visited[curName] = 1

        if not self.Order[curName].children or children_remain[curName] == 0:
            if curName == self.kingName:
                return 
            else: 
                self.Successor(self.Order[curName].parent, curOrder,visited,children_remain)
        else:
            children_remain[curName] -= 1
            self.Successor(self.Order[curName].children[len(self.Order[curName].children)-children_remain[curName]-1], curOrder,visited,children_remain)
            
        return


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)]
        
        
        

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

# [\"king\", \"andy\", \"matthew\", \"bob\", \"alex\", \"asha\", \"catherine\"]
# [\"king\", \"andy\", \"matthew\", \"alex\", \"asha\", \"catherine\"]


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.dic = dict()
        self.king = kingName
        self.dic[\"1_\"+kingName] = dict()
        self.direct = {kingName:self.dic[\"1_\"+kingName]}
        self.dead = set()
        

    def birth(self, parentName: str, childName: str) -> None:
        #名字上面加当前层的顺序
        if parentName in self.dead:
            return
        if parentName not in self.direct:
            return
        
        cur_dic = self.direct[parentName]
        order = str(len(cur_dic)+1) + \"_\"
        cur_dic[order + childName] = dict()
        self.direct[childName] = cur_dic[order + childName]

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

    def getInheritanceOrder(self) -> List[str]:
        res = []
            
        def compare1(s1, s2):
            s1 = int(s1.split(\"_\")[0])
            s2 = int(s2.split(\"_\")[0])
            if s1 < s2:
                return -1
            elif s1 > s2:
                return 1
            return 0
        def recur(parent):
            if parent not in self.dead:
                res.append(parent)
            cd = self.direct[parent]
            if len(cd) > 0:
                keys = sorted(list(cd.keys()), key=functools.cmp_to_key(compare1))
                # if parent == \"theresa\":
                    # print(parent, \"-\", keys)
                for c in keys:
                    c = c.split(\"_\")[1]
                    recur(c)
                    
        recur(self.king)
        return res
            


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.people = {kingName:[]}
        self.dead = dict()
        #storing the king name
        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 = []
        
        #Defining DFS function for finding all parents and their children 
        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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
        
            
            
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)
        # if ans: ans[0] = 'king'
        return ans


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class ThroneInheritance:

    def __init__(self, kingName: str):
        #what structure to use 
        #nested list, too hard to loop through?
        #list with tuples? 
        #dictionary with each person being a key and part of an array value
        #keep dictionary of dead people? 
        self.root = kingName
        self.inheritance = {kingName: []}
        self.dead = {}
        

    def birth(self, parentName: str, childName: str) -> None:
        #go through structure and add
        if parentName in self.inheritance:
            self.inheritance[parentName].append(childName)
        self.inheritance[childName] = []
            

    def death(self, name: str) -> None:
        #death doesn't affect successor function or current inheritance order
        #go through structure and delete
        self.dead[name] = 1

    def getInheritanceOrder(self) -> List[str]:
        #current order excluding dead people
        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
            


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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

class ThroneInheritance:

    def __init__(self, kingName: str):        
        self.root = Node(kingName)
        self.n2n = {kingName:self.root}
        self.dead = set()
        
    def birth(self, parentName: str, childName: str) -> None:
        node = Node(childName)
        self.n2n[parentName].children.append(node)
        self.n2n[childName] = node

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

    def getInheritanceOrder(self) -> List[str]:
        root = self.root
        res = []
        def dfs(root) -> None:
            if root.name not in self.dead:
                res.append(root.name)
            for child in root.children:
                dfs(child)
        dfs(root)
        return res
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]:
        # Traverse the tree
        ret = []
        # print(\"?\")    
        def dfs(node):
            # print(node.name)
            if node.alive:
                ret.append(node.name)
            for c in node.children:
                dfs(c)
    
        dfs(self.mapping[self.kingName])
        return ret


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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:
        
#         looking = parentName
#         while self.d[looking]:
#             looking = self.d[looking][-1]
        
#         # insert child into list
#         h = self.head
#         prev = h
#         while h != None:
#             prev = h
#             if h.val == looking:
#                 break
#             h = h.next
#         t = prev.next
#         prev.next = ListNode(childName, prev.next)
            
        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]:
        # ans = []
        # h = self.head
        # while h != None:
        #     if self.dead_people[h.val] == 0:
        #         ans.append(h.val)
        #     h = h.next
        # return ans
        return self.df('king')


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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:
        # import pprint
        # pprint.pprint(self.family)
        # pprint.pprint(self.parentChildrenDictMap)
        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
            
    
    


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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:
            # print(self.par)
            self.par[pN].append(cN)
        else:
            self.par[pN]=deque([cN])
        # print(self.par)

    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)
        # self.res=final
        return final
        
    def main(self):
        # cP=self.par.deepcopy()
        cC=self.child.copy()
        cP=copy.deepcopy(self.par)
        # print(cP, cC)
        # cP={}
        # for i in self.par:
        #     cP[i]=self.par[i]
        # print(cP)
        
        
    
        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:
                # print(self.par, cP)
                return res
        
        # return final


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


from collections import defaultdict

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.dead = defaultdict(bool)
        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[name] = True
        

    def getInheritanceOrder(self) -> List[str]:
        inheritanceOrder = []
        
        def traverse(member):
            if not self.dead[member]:
                inheritanceOrder.append(member)
            for child in self.members[member]:
                traverse(child)

        
        traverse(self.king)
        return inheritanceOrder


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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 getInheritanceOrder(self) -> List[str]:
        result = []
        def dfs(name):
            if name not in self.dead:
                result.append(name)
            for child in self.nation[name]:
                dfs(child)        
        
        dfs(self.king)
        return result


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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()


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
    
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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



# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()



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
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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):
        # preorder
        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
        

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()



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
        
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
            
            
            
            


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
        
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.nation = collections.defaultdict(list)
        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 getInheritanceOrder(self) -> List[str]:
        self.ans = []
        self.dfs(self.king)
        return self.ans
    
    def dfs(self, cur):
        if cur not in self.dead:
            self.ans.append(cur)
        for child in self.nation[cur]:
            self.dfs(child)


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


from collections import defaultdict

class ThroneInheritance:
    # inheritance = []
    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)
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class ThroneInheritance:

    def __init__(self, king: str):
        self.king = king
        # par -> children
        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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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 ThroneInheritance:

    def __init__(self, kingName: str):
        self.G = collections.defaultdict(list)
        self.dead = set()
        self.king = kingName
        self.parent = dict()
    def birth(self, parentName: str, childName: str) -> None:
        self.G[parentName].append(childName)
        self.parent[childName] = parentName
    def death(self, name: str) -> None:
        self.dead.add(name)

    def getInheritanceOrder(self) -> List[str]:
        toVisit = collections.defaultdict(int)
        visited = set()
        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
        
        \"\"\"         
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
\"\"\"
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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 getInheritanceOrder(self) -> List[str]:
        self.ans = []
        self.dfs(self.king)
        return self.ans
    
    def dfs(self, cur):
        if cur not in self.dead:
            self.ans.append(cur)
        for child in self.nation[cur]:
            self.dfs(child)


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)
        

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Person:
    
    def __init__(self, name: str) -> None:
        self.name = name
        self.children: List[\"Person\"] = list()
        self.alive = True


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.head: Person = Person(kingName)
        self.data = {kingName: self.head}
        

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


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

    def getInheritanceOrder(self) -> List[str]:
        
        seen, out = set(), []
        
        def _helper(node):
            if node not in seen:
                seen.add(node)
                if node.alive:
                    out.append(node.name)
                    
            for child in node.children:
                _helper(child)
                
        _helper(self.head)
        return out
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class TreeNode:

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


class ThroneInheritance:

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

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

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

    def getInheritanceOrder(self):
        \"\"\"
        This method derives the

        :return: Array of names by inheritance order
        :rtype: list[str]
        \"\"\"
        def recursive(head: TreeNode, inherit):
            if head.is_alive:
                inherit.append(head.name)
            for child in head.children:
                inherit = recursive(child, inherit)
            return inherit

        return recursive(self.root, [])


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
            
        
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.tree = {kingName: [True, []]}    # dict-tree, key--name, value--(alive, child_keys)
        

    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]]


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Tree:
    
    def __init__(self, name):
        \"\"\"
        name: name of the current tree
        child: list of children trees
        \"\"\"
        self.name = name
        self.child = []
        self.alive = True
        
class ThroneInheritance:

    def __init__(self, kingName: str):
        self.heritance = Tree(kingName)
        self.dict = {kingName: self.heritance}

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

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

    def getInheritanceOrder(self) -> List[str]:
        # would be a dfs of the whole tree
        # without the name of dead person
        order = []
        child = [self.heritance]
        while child:
            c = child.pop()
            if c.alive:
                order.append(c.name)
            for subchild in c.child[::-1]:
                child.append(subchild)
        
        return order
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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
            
            
    

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


#1600
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 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.node = {kingName: self.root}

    def birth(self, parentName: str, childName: str) -> None:
        child = Node(childName)
        self.node[parentName].addChild(child)
        self.node[childName] = child
            
    def death(self, name: str) -> None:
        self.node[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
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class TreeNode:

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


class ThroneInheritance:

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

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

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

    def getInheritanceOrder(self):
        \"\"\"

        :return: Array of names by inheritance order
        :rtype: list[str]
        \"\"\"
        def recursive(head: TreeNode):
            if head.is_alive:
                inherit = [head.name]
            else:
                inherit = []
            for child in head.children:
                inherit = inherit + recursive(child)
            return inherit

        return recursive(self.root)


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
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king_name =kingName
        self.inheritance_tree = {
            kingName:{
                \"children\":[],
                \"death\" : False
            },
            
        }

    def birth(self, parentName: str, childName: str) -> None:
        self.inheritance_tree[parentName][\"children\"].append(childName)
        self.inheritance_tree[childName] = {
                \"children\":[],
                \"death\" : False
        }

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


    def getInheritanceOrder(self) -> List[str]:
        
        res = []
        def helper(person,res):
            # print(self.inheritance_tree[person][\"children\"])
            if self.inheritance_tree[person][\"death\"] == False:
                res.append(person)

            if len(self.inheritance_tree[person]) == 0:
                return 

            for child in self.inheritance_tree[person][\"children\"]:
                helper(child,res)
        
        helper(self.king_name, res)

        return res


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class TreeNode:

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


class ThroneInheritance:

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

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

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

    def getInheritanceOrder(self):
        \"\"\"

        :return: Array of names by inheritance order
        :rtype: list[str]
        \"\"\"
        def recursive(head: TreeNode):
            if head is None:
                return []
            if head.is_alive:
                inherit = [head.name]
            else:
                inherit = []
            for child in head.children:
                inherit = inherit + recursive(child)
            return inherit

        return recursive(self.root)


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)
        
        
    


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)    


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Node(object):
    def __init__(self, name):
        self.name = name
        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:
        child = Node(childName)
        self.node[parentName].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
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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):
        #print(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)


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Person:
    
    def __init__(self, name: str) -> None:
        self.name = name
        self.children: List[\"Person\"] = list()
        self.alive = True
        self.next = self.prev = None


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.head: Person = Person(kingName)
        self.data = {kingName: self.head}
        

    def birth(self, parentName: str, childName: str) -> None:
        
        current = Person(childName)
        prev = self.data[parentName]
        while prev.children:
            prev = prev.children[-1]
            
        if prev.next is not None:
            next = prev.next
            prev.next, current.prev = current, prev
            current.next, next.prev = next, current
        else:
            prev.next, current.prev = current, prev
                
        self.data[parentName].children.append(current)
        self.data[childName] = current


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

    def getInheritanceOrder(self) -> List[str]:
        
        current, out = self.head, []
        while current is not None:
            if current.alive:
                out.append(current.name)
            current = current.next
        return out
        
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

from collections import OrderedDict
class ThroneInheritance:

    def __init__(self, kingName: str):
        # Maintain a tree
        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)
            

        
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Person:
    
    def __init__(self, name: str) -> None:
        self.name = name
        self.children: List[\"Person\"] = list()
        self.alive = True


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.head: Person = Person(kingName)
        self.data = {kingName: self.head}
        self.memo = (0, [])
        

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


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

    def getInheritanceOrder(self) -> List[str]:
        
        horizon, seen, out = [(self.head, iter(self.head.children))], set(), []
        while horizon:
            current, children_iter = horizon[-1]
            if current not in seen:
                seen.add(current)
                if current.alive:
                    out.append(current.name)
            try:
                child = next(children_iter)
            except StopIteration:
                horizon.pop()
                continue
            else:
                horizon.append((child, iter(child.children)))
                
        return out
        
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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
        
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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))


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]:
        # print(self.inh)
        order = [self.king]
        s = set(order)
        # inord = {k: cc[::-1] for k, (pp, _, cc) in self.inh.items()}
        def fs(x):
            p, a, ch = self.inh[x]
            # if not inord[x]: #  no children or all of x's children are in curOrder:
            #     if x != self.king:
            #         fs(p)
            # else:
            for c in ch:
                order.append(c)
                s.add(c)
                # inord[x].pop()
                fs(c)
        fs(self.king)
        return [o for o in order if self.inh[o][1]]


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()



#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.
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]
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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):
            # nonlocal ans
            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
            
            
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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.lastChild = {}
        
        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 parentName in self.lastChild:
            member = self.lastChild[parentName]
            member.nextSibling = child
        else:
            parent.nextChild = child
        self.lastChild[parentName] = 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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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)

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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;
        
        

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


class Node:
    def __init__(self, name):
        self.name = name
        self.children = []
        self.parent = None
        
    def add(self, child_node):
        self.children.append(child_node)
        child_node.parent = self
    
    def die(self):
        index = self.parent.children.index(self)
        #print(index, self.parent.children)
        self.parent.children[index:index] = self.children
        self.parent.children.remove(self) # remove from parents children
        for child in self.children:
            child.parent = self.parent
        self.parent = None


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.nodes = {}
        root = Node(\"\")
        self.nodes[\"\"] = root
        self.birth(\"\", kingName)
        
    def birth(self, parentName: str, childName: str) -> None:
        child = Node(childName)
        self.nodes[childName] = child
        parent = self.nodes[parentName]
        parent.add(child)

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

    def getInheritanceOrder(self) -> List[str]:
        path = []
        def dfs(node):
            path.append(node.name)
            for child in node.children:
                dfs(child)
        dfs(self.nodes[\"\"])
        return path[1:]
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

class Node:
    def __init__(self, val):
        self.val = val
        self.child = []   # list of Nodes
        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]:
        # dfs
        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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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]


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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

class ThroneInheritance:

    def __init__(self, kingName: str):
        
        self.root = TreeNode(kingName)
        self.mapping = collections.defaultdict()
        self.mapping[kingName] = self.root
        self.order = [kingName]
        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)
        \"\"\"if name == 'king' or self.root.val == name:
            siblings = self.root.children[1:]
            print(name, 'name')
            self.root = self.mapping[self.root.children[0]]
            # move all sibilings to new root's children
            self.root.siblings += siblings
        else:
            parent_node = self.parent[name]
            idx = self.mapping[parent_node].children.index(name)
            # move death's parent to its grandparent
            for child in reversed(self.mapping[name].children):
                self.parent[child] = parent_node
                self.mapping[parent_node].children.insert(idx, child)
            self.mapping[self.parent[name]].children.remove(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]
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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]:
        # apply DFS
        
        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

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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

    def __str__(self):
        parts = []
        parts.append(self.name)
        if self.alive == False:
            parts.append(\"dead\")
        parts.append(\"(\")
        for child in self.children:
            parts.append(child.name)
        parts.append(\")\")
        return \" \".join(parts)

class ThroneInheritance:

    def createPerson(self, name):
        p = Person(name)
        self.lookup[name] = p
        return p
    
    def __init__(self, kingName: str):
        self.lookup = dict()
        self.king = self.createPerson(kingName)
        
        print(self.lookup)
        print(self.king)

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

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

    def getInheritanceOrder(self) -> List[str]:
        order = []
        def doit(p):
            if p != None:
                if p.alive:
                    order.append(p.name)
                for c in p.children:
                    doit(c)
        doit(self.king)
        return order
        


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

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


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()


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