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:\n\n    def __init__(self, kingName: str):\n        self.graph = collections.defaultdict(list)\n        self.deaths = set()\n        self.root = kingName\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.graph[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.deaths.add(name)\n        \n    def inorder(self, root, res):\n        if root not in self.deaths:\n            res.append(root)\n        children = self.graph[root]\n        for child in children:\n            self.inorder(child, res)\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        self.inorder(self.root, res)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.graph = collections.defaultdict(list)\n        self.root = kingName\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.graph[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n    \n    def dfs(self, name, arr):\n        if name not in self.dead:\n            arr.append(name)\n        \n        for nei in self.graph[name]:\n            self.dfs(nei, arr)\n        \n        return arr\n    \n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        self.dfs(self.root, ans)\n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kName = kingName\n        self.dead = set()\n        self.cmap = {}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        cmap = self.cmap\n        if parentName not in self.cmap:\n            cmap[parentName] = []\n        cmap[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        # dfs\n        res = []\n        dfs(self.cmap, self.dead, self.kName, res)\n        return res\n    \ndef dfs(cmap, deaths, curr, res):\n    if curr == None:\n        return\n    if curr not in deaths:\n        res.append(curr)\n    if curr in cmap:\n        for child in cmap[curr]:\n            dfs(cmap, deaths, child, res)\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n\n# inheritance -> king is first member\n# 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.\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kn = kingName\n        # get_child[parent] = ([child in order], start_index)\n        self.get_child = {}\n        self.get_parent = {}\n        self.is_dead = set()\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        if parentName in self.get_child:\n            self.get_child[parentName][0].append(childName)\n        else:\n            self.get_child[parentName] = ([childName], 0)\n        self.get_parent[childName] = parentName\n\n    def death(self, name: str) -> None:\n        self.is_dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        cur_order = [self.kn]\n        cur_order_set = set()\n\n        def successor(x):\n            child = []\n            start_index = 0\n            if x in self.get_child:\n                child, start_index = self.get_child[x]\n            if len(child) == 0 or all([c in cur_order_set for c in child]):\n                if x == self.kn:\n                    return None\n                else:\n                    return successor(self.get_parent[x])\n            else:\n                for i in range(start_index, len(child)):\n                    c = child[i]\n                    if c not in cur_order_set:\n                        return c\n            assert False\n            return None\n        while cur_order[-1]:\n            s = successor(cur_order[-1])\n            cur_order.append(s)\n            cur_order_set.add(s)\n        final_cur_order = []\n        for co in cur_order:\n            if co and co not in self.is_dead:\n                final_cur_order.append(co)\n        return final_cur_order\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "#   \u591a\u53c9\u6811--\u524d\u5e8f\u904d\u5386\nclass Node:\n    def __init__(self, name):\n        self.val = name\n        self.children = []\n        self.alive = True\n    def birth(self, child):\n        self.children.append(child)\n    def death(self):\n        self.alive = False\n    def check_alive(self):\n        return self.alive\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        #   \u5929\u7136\u662f\u4e2a\u6811\u5f62\u7ed3\u6784\n        #   \u4e3a\u4e86\u751f\u548c\u6b7b\u7684\u5feb\u4e00\u4e9b\uff0c\u9700\u8981\u80fd\u591f\u901a\u8fc7\u540d\u5b57\u76f4\u63a5\u627e\u5230\u5404\u4e2a\u8282\u70b9\n        self.king = Node(kingName)\n        self.d    = dict()\n        self.d[kingName] = self.king\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.d[childName] = child\n\n        self.d[parentName].birth(child)\n        \n\n    def death(self, name: str) -> None:\n        self.d[name].death()\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        #   \u524d\u5e8f\u904d\u5386\uff0c\u53ea\u8bb0\u5f55\u6d3b\u7740\u7684\n        rtv = []\n        todo= []\n        todo.append(self.king)\n        while todo:\n            t = todo.pop()\n            if t.check_alive():\n                rtv.append(t.val)\n            for c in t.children[::-1]:\n                todo.append(c)\n        return rtv\n        \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n    class Person:\n        def __init__(self,name):\n            self.name = name\n            self.alive = True\n    def __init__(self, kingName: str):\n        self.tree = {}\n        self.king = self.Person(kingName)\n        self.name_map = {kingName:self.king}\n        self.tree[self.king] = []\n    \n    def printTree(self):\n        for p,v in self.tree.items():\n            print(p.name + \\\" : \\\" ,end = \\\" \\\")\n            for c in v:\n                print(c.name, end = \\\"  \\\")\n            print()\n    \n    def birth(self, parentName: str, childName: str) -> None:\n        child = self.Person(childName)\n        self.tree[self.name_map[parentName]].append(child)\n        self.name_map[childName] = child\n        self.tree[child] = []\n        #self.printTree()\n        \n\n    def death(self, name: str) -> None:\n        self.name_map[name].alive = False\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        inheritance = []\n        def rec(person):\n            if person.alive:\n                inheritance.append(person.name)\n            for child in self.tree[person]:\n                rec(child)\n        rec(self.king)\n        return inheritance\n                \n            \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.is_dead = False\n        self.children = []\n\nclass ThroneInheritance:    \n    def __init__(self, kingName: str):\n        self.king_name = kingName\n        self.nodes = {kingName: Node(kingName)}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.nodes[parentName]\n        child = Node(childName)\n        parent.children.append(child)\n        self.nodes[childName] = child\n\n    def death(self, name: str) -> None:\n        node = self.nodes[name]\n        node.is_dead = True\n        \n    def getInheritanceOrder(self) -> List[str]:\n        acc = []\n        def getInheritanceOrderRecursive(node):\n            if not node.is_dead:\n                acc.append(node.name)\n            for child in node.children:\n                getInheritanceOrderRecursive(child)\n        getInheritanceOrderRecursive(self.nodes[self.king_name])\n        return acc\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "#junge\n\nclass ThroneInheritance:\n    root = ''\n    children = {}\n    dead = {}\n\n    def __init__(self, kingName: str):\n        self.root = kingName\n        self.dead[self.root] = False\n        self.children = defaultdict(list)\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.children[parentName].append(childName)\n        self.dead[parentName] = False\n        self.dead[childName] = False\n\n    def death(self, name: str) -> None:\n        self.dead[name] = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        tosee = []\n        tosee.append(self.root);\n        while (len(tosee) != 0):\n            cur = tosee[0]\n            tosee.pop(0)\n\n            if (self.dead[cur] == False):\n                res.append(cur)\n\n            for item in reversed(self.children[cur]):\n                tosee.insert(0, item)\n\n        return res\n", "from collections import defaultdict\nclass Node:\n    def __init__(self, name):\n        self.name = name\n        #self.parent = None\n        self.childs = []\n        self.live = 1\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.p2cList = defaultdict(Node)\n        self.p2cList[kingName] = self.root\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        #child.parent = parentName\n        self.p2cList[parentName].childs.append(child)\n        self.p2cList[childName] = child\n        \n    def death(self, name: str) -> None:\n        self.p2cList[name].live = 0\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        cur = self.root\n        self.helper(res, cur)\n        return res\n    \n    def helper(self, res, cur):\n        if cur.live == 1:\n            res.append(cur.name)\n        if not cur.childs:\n            return\n        for childname in cur.childs:\n            self.helper(res, childname)\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "import collections\n\n\nclass ThroneInheritance(object):\n\n    def __init__(self, kingName):\n        \\\"\\\"\\\"\n        :type kingName: str\n        \\\"\\\"\\\"\n        self.__king = kingName\n        self.__family_tree = collections.defaultdict(list)\n        self.__dead = set()\n\n\n    def birth(self, parentName, childName):\n        \\\"\\\"\\\"\n        :type parentName: str\n        :type childName: str\n        :rtype: None\n        \\\"\\\"\\\"\n        self.__family_tree[parentName].append(childName)\n\n\n    def death(self, name):\n        \\\"\\\"\\\"\n        :type name: str\n        :rtype: None\n        \\\"\\\"\\\"\n        self.__dead.add(name)\n\n\n    def getInheritanceOrder(self):\n        \\\"\\\"\\\"\n        :rtype: List[str]\n        \\\"\\\"\\\"\n        result = []\n        stk = [self.__king]\n        while stk:  # preorder traversal\n            node = stk.pop()\n            if node not in self.__dead:\n                result.append(node)\n            if node not in self.__family_tree:\n                continue\n            for child in reversed(self.__family_tree[node]):\n                stk.append(child)\n        return result\n\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.G = collections.defaultdict(list)\n        self.dead = set()\n        self.king = kingName\n        self.parent = dict()\n    def birth(self, parentName: str, childName: str) -> None:\n        self.G[parentName].append(childName)\n        self.parent[childName] = parentName\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        toVisit = collections.defaultdict(int)\n        visited = set()\n        ans = []\n        def dfs(node, ans):\n            if node not in self.dead and node not in visited:\n                visited.add(node)\n                ans.append(node)\n            if toVisit[node] == len(self.G[node]):\n                if node == self.king:\n                    return \n                else:\n                    return dfs(self.parent[node], ans)\n            else:\n                toVisit[node] +=1\n                dfs(self.G[node][toVisit[node]-1], ans)\n        dfs(self.king, ans)\n        return ans\n        \n        \\\"\\\"\\\"         \nSuccessor(x, curOrder):\n    if x has no children or all of x's children are in curOrder:\n        if x is the king return null\n        else return Successor(x's parent, curOrder)\n    else return x's oldest child who's not in curOrder\n\\\"\\\"\\\"\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class ThroneInheritance:\n    \n    allNames={}\n\n    def __init__(self, kingName: str):\n        # order=[kingName]\n        # familyTree=Tree(kingName)\n        self.name=kingName\n        self.alive=True\n        self.children=[]\n        self.allNames[kingName]=self\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.allNames[parentName].children+=[ThroneInheritance(childName)]          \n\n    def death(self, name: str) -> None:\n        self.allNames[name].alive=False \n    \n    def getInheritanceOrder(self) -> List[str]:\n        answ=[]\n        if self.alive: answ+=[self.name]    \n        for child in self.children:\n            answ+=child.getInheritanceOrder()\n        return answ\n\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import defaultdict\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.dead = set()\n        self.members = defaultdict(list)        \n        self.king = kingName\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.members[parentName].append(childName)\n        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        inheritanceOrder = []\n        \n        def traverse(member):\n            if member not in self.dead:\n                inheritanceOrder.append(member)\n            for child in self.members[member]:\n                traverse(child)\n\n        \n        traverse(self.king)\n        return inheritanceOrder\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.dead_set = set()\n        self.children = collections.defaultdict(list)\n        self.inheritance_order = []\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        self.children[parentName].append(childName)\n        \n    def death(self, name: str) -> None:\n        self.dead_set.add(name)\n        \n    def successor(self, x):\n        if x not in self.dead_set:\n            self.inheritance_order.append(x)\n        \n        for child in self.children[x]:\n            self.successor(child) \n\n    def getInheritanceOrder(self) -> List[str]:\n        self.successor(self.king)\n        res = self.inheritance_order[:]\n        self.inheritance_order = []\n        return res\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Child:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.dead = False\n\ndef recursive(order):\n    if not order.dead:\n        out = [order.name]\n    else:\n        out = []\n    \n    for i in order.children:\n        out += recursive(i) \n    return out\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.order = Child(kingName)\n        self.dict = {kingName:self.order}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        b = Child(childName)\n        self.dict[parentName].children.append(b)\n        self.dict[childName] = b\n\n    def death(self, name: str) -> None:\n        self.dict[name].dead=True\n\n    def getInheritanceOrder(self) -> List[str]:\n                                              \n        return recursive(self.order)\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "\\\"\\\"\\\"\nSuccessor(x, curOrder):\n    if x has no children or all of x's children are in curOrder:\n        if x is the king return null\n        else return Successor(x's parent, curOrder)\n    else return x's oldest child who's not in curOrder\n\\\"\\\"\\\"\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.children = collections.defaultdict(list)\n        self.dead = set()\n        self.king = kingName\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        self.children[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n    \n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        visited = set()\n        self.dfs(self.king, res, visited)\n        if self.king not in self.dead:\n            return [self.king] + res\n        return res\n        \n    def dfs(self, node, res, visited):\n        for nxt in self.children[node]:\n            if nxt not in visited:\n                visited.add(node)\n                if nxt not in self.dead:\n                    res.append(nxt)\n                self.dfs(nxt, res, visited)\n            \n                \n        \n        \n            \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class Node:\n    def __init__(self, name):\n        self.children = []\n        self.name = name\n        \n    def add_children(self, name):\n        node = Node(name)\n        self.children.append(node)\n        return node\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.dead = set()\n        self.lookup = dict()\n        self.lookup[kingName] = self.root\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.lookup[childName] = self.lookup[parentName].add_children(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        results = []\n        \n        def dfs(x):\n            nonlocal results\n            \n            if x.name not in self.dead:\n                results.append(x.name)\n            for y in x.children:\n                dfs(y)\n            \n        dfs(self.root)\n        return results\n    \n    \n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.parent = {}\n        self.child  = {}\n        self.dead = set([])\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.addToHash(self.parent,childName, parentName)\n        \n        self.addToHash(self.child,parentName, childName)\n        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n    def succesor(self, name, curOrder):\n        if self.child.get(name):\n            for c in self.child.get(name):\n                if c not in curOrder:\n                    return c\n        if name == self.kingName:\n            return None\n        return self.succesor(self.parent[name][0], curOrder)\n    \n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        cur = self.kingName\n        inOrder = set([])\n        while cur:\n            if cur not in self.dead:\n                res.append(cur)\n            inOrder.add(cur)\n            cur = self.succesor(cur,inOrder)\n        return res\n            \n            \n        \n    def addToHash(self, hsh, key,value):\n        if hsh.get(key):\n            hsh.get(key).append(value)\n        else:\n            hsh[key] = [value]\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Tree: \n    def __init__(self, name, state = \\\"live\\\"): \n        self.children = []\n        self.name = name\n        self.state = state\n   \n    \nclass ThroneInheritance:\n    \n    king = \\\"\\\"\n    root = None\n    order = {}\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.root = Tree(kingName)\n        self.order[kingName] = self.root\n\n    def birth(self, parentName: str, childName: str) -> None:\n        node = Tree(childName)\n        \n        if parentName == self.king: \n            self.root.children.append(node)\n        else: \n            self.order[parentName].children.append(node)\n            \n        self.order[childName] = node\n\n    def death(self, name: str) -> None:\n        self.order[name].state = \\\"dead\\\"\n\n    def getInheritanceOrder(self) -> List[str]:\n        return self.preorder(self.root)\n            \n    def preorder(self, root): \n        if root is None: return []\n        \n        sk, out = [root, ], []\n    \n        while sk: \n            root = sk.pop()\n            if root.state == \\\"live\\\": \n                out.append(root.name)\n            sk.extend(root.children[::-1])\n            \n        return out\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class Tree:\n    def __init__(self, name):\n        self.val = name\n        self.descents = []\n        \n        \nclass ThroneInheritance:\n    \n    def __init__(self, kingName: str):\n        self.dic={}  # name:\u5b9e\u4f53\n        self.dead = set()\n        self.kingNode=Tree(kingName)\n        self.dic[kingName] = self.kingNode\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        if parentName not in self.dic:\n            node = Tree(parentName)\n            self.dic[parentName] = node\n        childNode = Tree(childName)\n        self.dic[childName] = childNode\n        self.dic[parentName].descents.append( childNode )\n        \n    def death(self, name: str) -> None:\n        self.dead.add(self.dic[name])\n\n        \n        \n    def output(self,root):\n        \n        if root not in self.dead:\n            self.ans.append(root.val)\n        for child in root.descents:\n            self.output(child)\n        \n        \n        \n    def getInheritanceOrder(self) -> List[str]:\n        self.ans=[]\n        self.output(self.kingNode)\n        return self.ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.live = True\n        self.children = []\n        \n    def death(self):\n        self.live = False\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.d = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.d[childName] = Node(childName)\n        self.d[parentName].children.append(self.d[childName])\n\n    def death(self, name: str) -> None:\n        self.d[name].death()\n\n    def getInheritanceOrder(self) -> List[str]:\n        def dfs(node, ans):\n            if node.live:\n                ans.append(node.name)\n            for ch in node.children:\n                dfs(ch, ans)\n        ans = []\n        dfs(self.root, ans)\n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "\n\nclass Family:\n    def __init__(self, parent):\n        self.parent = parent\n        self.children = []\n    \n    def __repr(self):\n        return f\\\"parent: {self.parent}, children: {self.children}\\\"\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.isdead = set()\n        self.hierarchy = defaultdict(Family)\n        self.hierarchy[kingName] = Family(None)\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.hierarchy[parentName].children.append(childName)\n        self.hierarchy[childName] = Family(parentName)\n        \n    def death(self, name: str) -> None:\n        self.isdead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:            \n        # def successor(x, curorder):\n        #     if not self.hierarchy[x].children or all(child in curorder for child in self.hierarchy[x].children):\n        #         if x == 'king': return None\n        #         else: return successor(self.hierarchy[x].parent, curorder)\n        #     else:\n        #         for child in self.hierarchy[x].children:\n        #             if child not in curorder:\n        #                 return child\n        # curorder = ['king']\n        # curorder_set = ('king')\n        # nxt = successor('king', curorder_set)\n        # while nxt:\n        #     curorder.append(nxt)\n        #     nxt = successor(curorder[-1], curorder)\n        \n        i = 0\n        curorderq, curorder = collections.deque(['king']), []\n        while curorderq:\n            curorder.append(curorderq.popleft())\n            if self.hierarchy[curorder[-1]].children:\n                for achild in self.hierarchy[curorder[-1]].children[::-1]:\n                    curorderq.appendleft(achild)\n        return [a for a in curorder if not a in self.isdead]\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.graph = collections.defaultdict(list)\n        self.deaths = set()\n        self.root = kingName\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.graph[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.deaths.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        result = []\n        def dfs(node, result):\n            if node not in self.deaths:\n                result.append(node)\n            children = self.graph[node]\n            for child in children:\n                dfs(child, result)\n        \n        dfs(self.root, result)\n        return result\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.children = list()\n        self.alive = True\n    \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.map = defaultdict(Node)\n        self.map[kingName] = Node(kingName)\n        self.parent = defaultdict(str)\n        self.king = kingName\n        self.curOrder = [kingName]\n    def birth(self, parentName: str, childName: str) -> None:\n        self.map[childName] = Node(childName)\n        self.map[parentName].children.append(childName)\n        self.parent[childName] = parentName\n        \n    def death(self, name: str) -> None:\n        self.map[name].alive = False\n    # @lru_cache(None)\n    def Successor(self, x):\n        # print(self.map, self.parent)\n        # print(x, self.curOrder)\n        # self.curOrder += [x]\n        flag = False\n        for child in self.map[x].children:\n            if child not in self.currSet:\n                break\n        else:\n            flag = True\n        if not self.map[x].children or flag: #all of x's children are in curOrder:\n            if x == self.king:\n                return None\n            else: \n                return self.Successor(self.parent[x])\n        else:\n            # return x's oldest child who's not in curOrder\n            for child in self.map[x].children:\n                if child not in self.currSet:\n                    return child\n            return None\n    def getInheritanceOrder(self) -> List[str]:\n        self.curOrder = []\n        self.currSet = set()\n        name = self.king\n        while name:\n            self.curOrder.append(name)\n            self.currSet.add(name)\n            name = self.Successor(name)\n        return [a for a in self.curOrder if self.map[a].alive]\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n    \n    def __init__(self, kingName: str):\n        self.nation = defaultdict(list)\n        self.king = kingName\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.nation[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n    def dfs(self, person):\n        if person not in self.dead:\n            self.ans.append(person)\n        for child in self.nation[person]:\n            self.dfs(child)\n            \n    def getInheritanceOrder(self) -> List[str]:\n        self.ans = []\n        self.dfs(self.king)\n        return self.ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from functools import lru_cache\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.pm = {}\n        self.cm = {}\n        self.p = {\n            kingName: True\n        }\n        self.king = kingName\n        self.cm[kingName] = []\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.pm[childName] = parentName\n        \n        self.cm[parentName].append(childName)\n\n        self.cm[childName] = []\n\n        self.p[childName] = True\n\n    def death(self, name: str) -> None:\n        self.p[name] = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        x = self.king\n        curOrder = [x]\n\n        marked_childs = {}\n        queue_childs = {}\n\n        for p, v in self.cm.items():\n            marked_childs[p] = set()\n            queue_childs[p] = v[:]\n\n        while True:\n            res = self.successor(x, marked_childs, queue_childs)\n            if res == None:\n                break\n            curOrder.append(res)\n            x = res\n        ans = []\n        for p in curOrder:\n            if self.p[p]:\n                ans += [p]\n        return ans\n        \n    def successor(self, x, marked_childs, queue_childs):\n        if len(self.cm[x]) == 0 or len(queue_childs[x]) == 0:\n            if self.king == x:\n                return None\n            else:\n                return self.successor(self.pm[x], marked_childs, queue_childs)\n        else:\n            c = queue_childs[x].pop(0)\n            marked_childs[x] = c\n            return c", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.children = defaultdict(list)\n        self.parent = {}\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.children[parentName].append(childName)\n        self.parent[childName] = parentName\n        \n    def successor(self, name):\n        for child in self.children[name]:\n            if child not in self.order_set:\n                self.order_set.add(child)\n                self.curOrder.append(child)\n                return child\n        if name != self.kingName:\n            return self.successor(self.parent[name])\n        return None\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        self.curOrder = [self.kingName]\n        self.order_set = set(self.curOrder)\n        name = self.kingName\n        while name:\n            name = self.successor(name)\n        return [name for name in self.curOrder if name not in self.dead]\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import defaultdict\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.family = defaultdict(list)\n        self.parents = {}\n        self.dead = set()\n        self.size = 1\n            \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.family[parentName].append(childName)\n        self.parents[childName] = parentName\n        self.size +=1\n\n    def death(self, name: str) -> None:\n        # del self.family[name]\n        self.dead.add(name)\n        # if name == self.king:\n            # self.king = self.getInheritanceOrder()[1]\n        # self.size -= 1\n        \n    def getInheritanceOrder(self) -> List[str]:\n        ans = [self.king]\n        pool = set(self.king)\n        def sccesssor(x, curOrder):\n            # print(x, f\\\"{curOrder=}\\\")\n            if self.family[x] == [] or set(self.family[x]) <= pool:\n                if x == self.king:\n                    return\n                else:\n                    sccesssor(self.parents[x], curOrder)\n            else:\n                for name in self.family[x]:\n                    # print(name)\n                    if name not in pool:\n                        curOrder.append(name)\n                        pool.add(name)\n                        return\n            \n        for i in range(self.size-1):\n            if ans[-1] in self.dead:\n                dead = ans.pop()\n                sccesssor(dead, ans)\n            else:\n                sccesssor(ans[-1], ans)\n        if ans[-1] in self.dead:\n                ans.pop()      \n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.d = defaultdict(list)\n        self.deads = set()\n        self.k = kingName\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.d[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.deads.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        arr = []\n        def getChildren(name):\n            if name not in self.deads:\n                arr.append(name)\n            for child in self.d[name]:\n                getChildren(child)\n        \n        getChildren(self.k)\n        return arr\n        \n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person(object):\n    def __init__(self, name, p_name, live=True):\n        self.name = name\n        self.p_name = p_name\n        self.live = live\n        self.sibling = None\n        self.first_child = None\n        #######################################################\n        # optimization 1: remember last_child for chain in O(1)  \n        #######################################################\n        self.last_child = None\n\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.curOrder = [kingName]\n        self.curOrder_pos = {}\n        self.inherit_pos = float('inf')\n        self.person_map = {}\n        self.person_map[kingName] = Person(kingName, None)\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.person_map[parentName]\n        children = parent.first_child\n        # first child\n        if children == None:\n            parent.first_child = Person(childName, parentName)\n            self.person_map[childName] = parent.first_child\n            parent.last_child = parent.first_child\n            #print('1 children:', parent.children.name, 'parent:', parent.children.p_name)\n            #print('1 self.person_map=', self.person_map)\n            #print('------')\n        else:\n            # add after last child\n            parent.last_child.sibling = Person(childName, parentName)\n            parent.last_child = parent.last_child.sibling\n            self.person_map[childName] = parent.last_child\n            #print('3 children:', children.name, 'parent:', children.p_name)\n            #print('3 children.sibling:', children.sibling.name, 'parent:', children.sibling.p_name)\n            #print('3 self.person_map=', self.person_map)\n            #print('------')\n            \n        if parentName in self.curOrder_pos:\n            self.inherit_pos = min(self.inherit_pos, self.curOrder_pos[parentName])\n            \n            \n    def death(self, name: str) -> None:\n        self.person_map[name].live = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        # if x has no children or all of x's children are in curOrder:\n        #    if x is the king return null\n        #    else return Successor(x's parent, curOrder)\n        # else return x's oldest child who's not in curOrder\n        def successor(person_map, x, curOrder, curOrder_pos):\n            p = person_map[x]\n            # check if all p's children are in curOrder\n            c = p.first_child\n            o_c = None\n            while c:\n                #####################################\n                # optimization 2: O(1) search in dict  \n                #####################################\n                if c.name not in curOrder_pos:\n                    o_c = c\n                    break\n                c = c.sibling\n                \n            if (not p.first_child) or (not o_c):\n                return None if x == curOrder[0] else successor(person_map, p.p_name, curOrder, curOrder_pos)\n            else:\n                return o_c.name\n            \n        if self.inherit_pos != float('inf'):\n            for i in range(self.inherit_pos+1, len(self.curOrder)):\n                del self.curOrder_pos[self.curOrder[i]]\n            ###################################################################\n            # optimization 3: only recalculate inheritence from parent impacted  \n            ###################################################################\n            self.curOrder = self.curOrder[:self.inherit_pos+1]\n            \n            \n        nxt = successor(self.person_map, self.curOrder[-1], self.curOrder, self.curOrder_pos)\n        while nxt:\n            self.curOrder.append(nxt)\n            self.curOrder_pos[nxt] = len(self.curOrder)-1\n            nxt = successor(self.person_map, nxt, self.curOrder, self.curOrder_pos)\n            \n        result = []\n        for i, x in enumerate(self.curOrder):\n            if self.person_map[x].live:\n                result.append(x)\n            \n        self.inherit_pos = float('inf')\n        return result\n            \n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.isAlive = True\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = Node(kingName)\n        self.directory = {kingName: self.king}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parentnode = self.directory[parentName]\n        childnode = Node(childName)\n        parentnode.children.append(childnode)\n        self.directory[childName] = childnode\n\n    def death(self, name: str) -> None:\n        self.directory[name].isAlive = False\n        \n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        def dfs(node):\n            if not node: return\n            if node.isAlive:\n                ans.append(node.name)\n            for child in node.children:\n                dfs(child)\n        dfs(self.king)\n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.start = kingName\n        self.deaths = {}\n        self.relat = collections.defaultdict(list)\n        self.relat[kingName] = []\n        self.n = 1\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.relat[parentName].append(childName)\n        self.n += 1\n\n    def death(self, name: str) -> None:\n        self.deaths[name] = True\n        \n    def getInheritanceOrder(self) -> List[str]:\n        ret = []\n        q = [self.start]\n        while q:\n            cur = q.pop()\n            if cur not in self.deaths:\n                ret.append(cur)\n            for nxt in self.relat[cur][::-1]:\n                q.append(nxt)\n        return ret\n                \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.parents = {}\n        self.children = collections.defaultdict(list)\n        self.dead = set()\n    \n    def Successor(self, x, cur_order):\n        x_children = self.children.get(x, [])\n        cand = None\n        for c in x_children:\n            if c not in cur_order:\n                cand = c\n                break\n        if len(x_children) == 0 or cand is None:\n            if x == self.king:\n                return None\n            else:\n                return self.Successor(self.parents[x], cur_order)\n        else:\n            return cand\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.parents[childName] = parentName\n        self.children[parentName].append(childName)\n        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        suc = self.king\n        cur_order = set([suc])\n        while suc:\n            if suc not in self.dead:\n                res.append(suc)\n            cur_order.add(suc)\n            suc = self.Successor(suc, cur_order)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.died = set()\n        self.hmap = defaultdict(lambda : list())\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.hmap[parentName].append(childName)\n        \n    def death(self, name: str) -> None:\n        self.died.add(name)\n        \n    def getInheritanceOrder(self) -> List[str]:\n        res = list()\n        q = [\\\"king\\\"]\n        \n        while q:\n            name = q.pop()\n            \n            if name not in self.died:\n                res.append(name)\n                \n            for child in self.hmap[name][::-1]:\n                q.append(child)\n                \n        return res\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class Person:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.alive = True\n        self.parent = None\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = Person(kingName)\n        self.people = {kingName: self.king}\n        \n    def successor(self, x, current_order):\n        stack = [x]\n        while len(stack) > 0:\n            t = stack.pop()\n            if t.alive:\n                current_order.append(t)\n            for i in t.children:\n                stack.append(i)\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.people.get(parentName)\n        child = Person(childName)\n        self.people[childName] = child\n        child.parent = parent\n        parent.children = [child] + parent.children\n\n    def death(self, name: str) -> None:\n        p = self.people.get(name)\n        p.alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        result = []\n        self.successor(self.king, result)\n        return [i.name for i in result]\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.nation = defaultdict(list)\n        self.king = kingName\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.nation[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        self.ans = []\n        self.dfs(self.king)\n        return self.ans\n    \n    def dfs(self, cur):\n        if cur not in self.dead:\n            self.ans.append(cur)\n        for child in self.nation.get(cur,()):\n            self.dfs(child)", "\nclass people:\n    def __init__(self, name):\n        self.name = name\n        self.son = []\n        self.alive = True\nclass ThroneInheritance:\n    \n\n    def __init__(self, kingName: str):\n        self.king = people(kingName)\n        self.all_people = {}\n        self.all_people[kingName] = self.king\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        self.all_people[childName] = people(childName)\n        p = self.all_people[parentName]\n        p.son.append(self.all_people[childName])\n        \n    def death(self, name: str) -> None:\n        self.all_people[name].alive = False\n        \n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        p = self.king\n        stack = []\n        while p or stack:\n            if p.alive:\n                ans.append(p.name)\n            if p.son:\n                for i in reversed(p.son[1:]):\n                    stack.append(i)\n                p = p.son[0]\n            elif stack:\n                p = stack.pop()\n            else:\n                p = None\n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, val):\n        self.val = val\n        self.child = None\n        self.next = None\n        self.prev = None\n        self.parent = None\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.throne = Node(kingName)\n        self.nodes = dict()\n        self.nodes[kingName] = self.throne\n    \n    def birth(self, parentName: str, childName: str) -> None:\n        node = self.nodes[parentName]\n        if node.child:\n            child = node.child\n            while child.__next__ != None:\n                child = child.__next__\n            child.next = Node(childName)\n            child.next.prev = child\n            child.next.parent = node\n            self.nodes[childName] = child.__next__\n        else:\n            node.child = Node(childName)\n            node.child.parent = node\n            self.nodes[childName] = node.child\n        \n    def death(self, name: str) -> None:\n        \n        del self.nodes[name]\n            \n            \n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        if not self.throne:\n            return None\n        \n        stack = [self.throne]\n        while stack:\n            curr = stack.pop()\n            if curr.val in self.nodes:\n                order.append(curr.val)\n            \n            if curr.__next__:\n                stack.append(curr.__next__)\n            if curr.child:\n                stack.append(curr.child)\n        return order\n#[\\\"king\\\", \\\"andy\\\", \\\"matthew\\\", \\\"bob\\\", \\\"alex\\\", \\\"asha\\\", \\\"catherine\\\"]\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n\n# [\\\"ThroneInheritance\\\",\\\"birth\\\",\\\"birth\\\",\\\"birth\\\",\\\"getInheritanceOrder\\\"]\n# [[\\\"king\\\"],[\\\"king\\\",\\\"andy\\\"],[\\\"king\\\",\\\"bob\\\"],[\\\"andy\\\",\\\"matthew\\\"],[null]]\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.alive = True\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.people = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.people[parentName].children.append(child)\n        self.people[childName] = child\n\n    def death(self, name: str) -> None:\n        self.people[name].alive = False\n        \n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        self.helper(self.root, res)\n        return res\n        \n    def helper(self, root, res):\n        if root.alive:\n            res.append(root.name)\n        if not root.children:\n            return\n        for child in root.children:\n            self.helper(child, res)\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class people:\n    \n    def __init__(self, name):\n        self.name = name\n        self.alive = True\n        self.children = []\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.dic = {}\n        self.dic[kingName] = people(kingName)\n    def birth(self, parentName: str, childName: str) -> None:\n        child = people(childName)\n        self.dic[childName] = child\n        self.dic[parentName].children.append(child)\n    \n    def death(self, name: str) -> None:\n        self.dic[name].alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = self.dfs(self.dic[self.kingName])\n        res = []\n        for o in order:\n            if o.alive is True:\n                res.append(o.name)\n        return res\n    def dfs(self, cur):\n        res = []\n        res.append(cur)\n        for child in cur.children:\n            temp = self.dfs(child)\n            res += temp\n        return res\n            \n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        dummy = TreeNode('', None)\n        self.root = dummy\n        self.lookup = {}\n        \n        self._addNode(kingName, dummy)\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self._addNode(childName, self.lookup[parentName])\n\n    def death(self, name: str) -> None:\n        if name not in self.lookup:\n            return\n        \n        node = self.lookup[name]\n        #no children\n        if node.firstChild.next.name == '':\n            node.prev.next = node.next\n            node.next.prev = node.prev\n        else:\n            firstChild = node.firstChild.next\n            lastChild = node.lastChild.prev\n            node.prev.next = firstChild\n            firstChild.prev = node.prev\n            node.next.prev = lastChild\n            lastChild.next = node.next\n            \n        del node        \n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        self._dfs(self.root, res)\n        return res\n        \n    def _dfs(self, cur, res):\n        if not cur:\n            return\n        \n        if cur.name != '':\n            res.append(cur.name)\n            \n        child = cur.firstChild\n        while child:\n            self._dfs(child, res)\n            child = child.next\n        \n    def _addNode(self, name, parentNode):\n        node = TreeNode(name, parentNode)\n        self.lookup[name] = node\n        \n        prev = parentNode.lastChild.prev\n        nxt = parentNode.lastChild\n        node.prev = prev\n        node.next = nxt\n        prev.next = node\n        nxt.prev = node\n        \n    def _print(self, name, node):\n        print(name)\n        while node:\n            print(node.name + \\\"+\\\")\n            node = node.next\n        \nclass TreeNode:\n    def __init__(self, name, parent):\n        self.name = name\n        self.parent = parent\n        self.next = None\n        self.prev = None\n        self.firstChild = DummyNode()\n        self.lastChild = DummyNode()\n        \n        self.firstChild.next = self.lastChild\n        self.lastChild.prev = self.firstChild\n        \nclass DummyNode:\n    def __init__(self):\n        self.name = ''\n        self.next = None\n        self.prev = None\n        self.firstChild = None\n        self.lastChild = None\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class ThroneInheritance:\n    import collections\n    \n    def __init__(self, kingName: str):\n        self.king_name = kingName\n        self.dead = set([]) # names of dead people\n        self.children = collections.defaultdict(list)\n        self.parent = {}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.children[parentName].append(childName)\n        self.parent[childName] = parentName\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        order = [self.king_name]\n        order_set = set(order)\n        \n        def successor(x):\n            ys = [y for y in self.children[x] if y not in order_set]\n            if not ys:\n                if x == self.king_name:\n                    return None\n                return successor(self.parent[x])\n\n            y = ys[0]\n            order.append(y)\n            order_set.add(y)\n            return y\n\n        p = successor(self.king_name)\n        while p:\n            p = successor(p)                \n        \n        return [name for name in order if name not in self.dead]\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "import copy\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.parent = collections.defaultdict(list) # child : parent\n        self.children = collections.defaultdict(list) # parent: children\n        self.king = kingName\n        self.deathList = set()\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        self.parent[childName].append(parentName)\n        self.children[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.deathList.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = [self.king]\n        current = self.king\n        #print(self.parent, self.children)\n        c = copy.deepcopy(self.children)\n        p = copy.copy(self.parent)\n        def Successor(x, curOrder):\n            if x not in c or len(c[x]) == 0:\n                if x == self.king:\n                    return None\n                else:\n                    return Successor(p[x][0], curOrder)\n            newx = c[x].pop(0)\n            curOrder.append(newx)\n            return newx\n            \n        while current:\n            current = Successor(current, order)\n            \n        if not self.deathList:\n            return order\n        else:\n            neworder = []\n            for name in order:\n                if name not in self.deathList:\n                    neworder.append(name)\n            return neworder\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.hm = { kingName: self.root }\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        pnode = self.hm[parentName]\n        cNode = Node(childName)\n        self.hm[childName] = cNode\n        pnode.children.append(cNode)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        \n        def dfs(node):\n            if node.name not in self.dead:\n                res.append(node.name)\n            for child in node.children:\n                dfs(child)\n        \n        dfs(self.root)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.parent = defaultdict(str)\n        self.children = defaultdict(list)\n        self.king = kingName\n        self.order = []\n        self.orderset = set()\n        self.dead = set()\n\n    def birth(self, p: str, c: str) -> None:\n        self.parent[c] = p\n        self.children[p].append(c)\n        #print(self.parent)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        self.order = [self.king]\n        self.orderset = set([self.king])\n        while self.getNext(self.order[-1]):\n            temp = self.getNext(self.order[-1])\n            self.order.append(temp)\n            self.orderset.add(temp)\n        res = []\n        for ele in self.order:\n            if ele not in self.dead:\n                res.append(ele)\n        return res\n    \n    def getNext(self, cur):\n        if not self.children[cur] or self.check(cur):\n            if cur == self.king:\n                return None\n            else:\n                return self.getNext(self.parent[cur])\n        else:\n            for child in self.children[cur]:\n                if child not in self.orderset:\n                    return child\n    \n    def check(self, cur):\n        for child in self.children[cur]:\n            if child not in self.orderset:\n                return False\n        return True\n            \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Family:\n    def __init__(self, name):\n        self.dead = False\n        self.children = []\n        self.name = name\n    \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.family_map = {}\n        member = Family(kingName)\n        self.family_map[kingName] = member\n        self.king = member\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        member = self.family_map[parentName]\n        child = Family(childName)\n        member.children.append(child)\n        self.family_map[childName] = child\n\n    def death(self, name: str) -> None:\n        member = self.family_map[name]\n        member.dead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        # dfs with living members\n        inheritance = []\n        stack = [self.king]\n        \n        while len(stack):\n            member = stack.pop()\n            for child in member.children[::-1]:\n                stack.append(child)\n            if not member.dead:\n                inheritance.append(member.name)\n        \n        return inheritance\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.descs = defaultdict(list)\n        self.dead = set()        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.descs[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        stack = [self.king]\n        \n        ans = []\n        \n        while stack:\n            heir = stack.pop()\n            if heir not in self.dead:\n                ans.append(heir) \n            stack += self.descs[heir][::-1]\n        \n        return ans\n        \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.prev = None\n        self.next = None\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.deaths = set()\n        self.deaths.add(\\\"\\\")\n        self.nameToNode = {}\n        self.head = Node(\\\"\\\")\n        self.tail = Node(\\\"\\\")\n        self.kingName = kingName\n        \n        king = Node(kingName)\n        self.head.next = king\n        king.next = self.tail\n        self.tail.prev = king\n        king.prev = self.head\n        \n        self.nameToNode[kingName] = {\\\"node\\\": king, \\\"children\\\": [], \\\"parent\\\": None}\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.nameToNode[parentName]\n        prev_node = parent[\\\"node\\\"]\n        if parent[\\\"children\\\"]:\n            prev_node = parent[\\\"children\\\"][-1]\n            while self.nameToNode[prev_node.name][\\\"children\\\"]:\n                prev_node = self.nameToNode[prev_node.name][\\\"children\\\"][-1]\n        \n        c_node = Node(childName)\n        parent[\\\"children\\\"].append(c_node)\n        self.nameToNode[childName] = {\\\"node\\\":c_node, \\\"children\\\":[], \\\"parent\\\": parent[\\\"node\\\"]}\n        \n        post_node = prev_node.next\n        prev_node.next = c_node\n        c_node.next = post_node\n        post_node.prev = c_node\n        c_node.prev = prev_node\n        \n\n    def death(self, name: str) -> None:\n        self.deaths.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        node = self.nameToNode[self.kingName][\\\"node\\\"]\n        res = []\n        while node:\n            if node.name not in self.deaths:\n                res.append(node.name)\n            node = node.next\n        return res\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class Node(object):\n    def __init__(self, name, parent=''):\n        self.name = name\n        self.parent = parent\n        self.children = []\n        \n    def addChild(self, child):\n        self.children.append(child)\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.node = {kingName: self.root}\n        self.deaths = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.node[parentName].addChild(childName)\n        self.node[childName] = Node(childName, parentName)\n\n    def death(self, name: str) -> None:\n        self.deaths.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = [self.root.name]\n        seen = set(order)\n        def successor(nodeName):\n            node = self.node[nodeName]\n            if (not node.children or all(c in seen for c in node.children)):\n                if nodeName == self.root.name:\n                    return\n                return successor(node.parent)\n            for c in node.children:  \n                if c not in seen:\n                    seen.add(c)\n                    order.append(c)\n                    return c\n        while (name := successor(order[-1])):\n            pass\n        return [o for o in order if o not in self.deaths]\n                \n                \n        \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    def __init__(self, name, parent=None, children=[], isdead = False):\n        self.name = name\n        self.children = children\n        self.parent = parent\n        self.isdead = False\n\n        \n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        kingNode = Person(kingName, parent=\\\"kingfather\\\",children=[],isdead =False)\n        self.Order = {kingName:kingNode}\n\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        self.Order[childName] = Person(childName,parent=parentName,children=[],isdead = False)\n        self.Order[parentName].children.append(childName)\n        \n\n    def death(self, name: str) -> None:\n        self.Order[name].isdead = True\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        children_remain = {}\n        for key,val in self.Order.items():\n            \n            children_remain[key] = len(self.Order[key].children)\n\n        \n        curOrder = []\n        visited = {}\n\n        self.Successor(self.kingName,curOrder,visited,children_remain)\n        return curOrder\n\n        \n    def Successor(self,curName,curOrder,visited,children_remain):\n        \n        \n        # print(self.Order[curName].children)\n        # print(children_remain[curName])\n        if self.Order[curName].isdead == False and curName not in visited:\n            curOrder.append(curName)\n            visited[curName] = 1\n\n        if not self.Order[curName].children or children_remain[curName] == 0:\n            if curName == self.kingName:\n                return \n            else: \n                self.Successor(self.Order[curName].parent, curOrder,visited,children_remain)\n        else:\n            children_remain[curName] -= 1\n            self.Successor(self.Order[curName].children[len(self.Order[curName].children)-children_remain[curName]-1], curOrder,visited,children_remain)\n            \n        return\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class TreeNode:\n    \n    def __init__(self, val=None):\n        self.val = val\n        self.children = []\n        self.parent = None\n        \n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        \n        self.dic = {}\n        self.root = TreeNode(kingName)\n        self.dic[kingName] = self.root\n        self.dead = {}\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        parent_node = self.dic[parentName]\n        child_node = TreeNode(childName)\n        child_node.parent = parent_node\n        self.dic[childName] = child_node\n        parent_node.children.append(child_node)\n        \n        \n\n    def death(self, name: str) -> None:\n        \n        self.dead[name] = True\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        order_lst = []\n        def recurse(root):\n            if root.val not in self.dead:\n                order_lst.append(root.val)\n            for child in root.children:\n                recurse(child)\n                \n        recurse(self.root)\n        return order_lst\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class P:\n    def __init__(self, name):\n        self.name = name\n        self.child = []\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = P(kingName)\n        self.d = {kingName:self.king}\n        self.dead = set()\n\n    def getnext(self,k):\n        if k.name not in self.dead:\n            yield k.name\n            \n        for c in k.child:\n            yield from self.getnext(c)\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        child = P(childName)\n        self.d[childName] = child\n        self.d[parentName].child.append(child)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        return [*self.getnext(self.king)]\n        \n        \n        \n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n\n# [\\\"king\\\", \\\"andy\\\", \\\"matthew\\\", \\\"bob\\\", \\\"alex\\\", \\\"asha\\\", \\\"catherine\\\"]\n# [\\\"king\\\", \\\"andy\\\", \\\"matthew\\\", \\\"alex\\\", \\\"asha\\\", \\\"catherine\\\"]\n", "from collections import defaultdict\n\nclass Person:\n    def __init__(self, name, parent):\n        self.name = name\n        self.is_alive = True\n        self.parent = parent\n        self.children = []\n\n    def has_children(self):\n        return True if len(self.children) > 0 else False\n\n    def add_child(self, child):\n        self.children.append(child)\n\nclass Order:\n    def __init__(self):\n        self.order = []\n        self.names_set = set()\n\n    def add(self, person):\n        self.order.append(person)\n        self.names_set.add(person.name)\n\n    def not_in(self, persons):\n        res = []\n        for p in persons:\n            if p.name not in self.names_set:\n                res.append(p)\n        return res\n\n\n\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.family = defaultdict(Person)\n        self.king = Person(kingName, None)\n        self.family[kingName] = self.king\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.family[parentName]\n        new_child = Person(childName, parent)\n        self.family[childName] = new_child\n        self.family[parentName].add_child(new_child)\n\n\n    def death(self, name: str) -> None:\n        self.family[name].is_alive = False\n\n    def getInheritanceOrder(self) -> 'List[str]':\n        def successor(person, cur_order):\n            children_not_in_order = cur_order.not_in(person.children)\n            if not person.has_children() or not children_not_in_order:\n                if person.parent is None:\n                    return None\n                else:\n                    return successor(person.parent, cur_order)\n            else:\n                return children_not_in_order[0]\n\n        order = Order()\n\n        next_in_order = self.king\n        while next_in_order:\n            order.add(next_in_order)\n            next_in_order = successor(next_in_order, order)\n\n        res = []\n        for p in order.order:\n            if p.is_alive:\n                res.append(p.name)\n\n        return res", "\nclass ThroneInheritance:\n    \n    def __init__(self, kingName: str):\n        self.dic = dict()\n        self.king = kingName\n        self.dic[\\\"1_\\\"+kingName] = dict()\n        self.direct = {kingName:self.dic[\\\"1_\\\"+kingName]}\n        self.dead = set()\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        #\u540d\u5b57\u4e0a\u9762\u52a0\u5f53\u524d\u5c42\u7684\u987a\u5e8f\n        if parentName in self.dead:\n            return\n        if parentName not in self.direct:\n            return\n        \n        cur_dic = self.direct[parentName]\n        order = str(len(cur_dic)+1) + \\\"_\\\"\n        cur_dic[order + childName] = dict()\n        self.direct[childName] = cur_dic[order + childName]\n\n    def death(self, name: str) -> None:\n        if name not in self.direct:\n            return\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n            \n        def compare1(s1, s2):\n            s1 = int(s1.split(\\\"_\\\")[0])\n            s2 = int(s2.split(\\\"_\\\")[0])\n            if s1 < s2:\n                return -1\n            elif s1 > s2:\n                return 1\n            return 0\n        def recur(parent):\n            if parent not in self.dead:\n                res.append(parent)\n            cd = self.direct[parent]\n            if len(cd) > 0:\n                keys = sorted(list(cd.keys()), key=functools.cmp_to_key(compare1))\n                # if parent == \\\"theresa\\\":\n                    # print(parent, \\\"-\\\", keys)\n                for c in keys:\n                    c = c.split(\\\"_\\\")[1]\n                    recur(c)\n                    \n        recur(self.king)\n        return res\n            \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.people = {kingName:[]}\n        self.dead = dict()\n        #storing the king name\n        self.kn = kingName\n\n    def birth(self, parentName: str, childName: str) -> None:\n        if self.people.get(parentName, 0) != 0:\n            self.people[parentName].append(childName)\n        else:\n            self.people[parentName] = [childName]\n\n    def death(self, name: str) -> None:\n        self.dead[name] = 1\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        \n        #Defining DFS function for finding all parents and their children \n        def dfs(curr, res):\n            if self.dead.get(curr, 0) == 0:\n                res.append(curr)\n            if curr in list(self.people.keys()):\n                for i in self.people[curr]:\n                    dfs(i, res)\n                    \n        dfs(self.kn, res)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.g=collections.defaultdict(list)\n        self.rg={}\n        self.ROOT=kingName\n        self.deathS=set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.g[parentName].append(childName)\n        self.rg[childName]=parentName\n\n    def death(self, name: str) -> None:\n        self.deathS.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        def succeed(x, currentOrder):\n            if x:\n                if len(self.g[x])==0 or all(i in currentOrder for i in self.g[x]):\n                    if x==self.ROOT:\n                        return None\n                    else:\n                        return succeed(self.rg[x],currentOrder)\n                else:\n                    for i in self.g[x]:\n                        if i not in currentOrder:\n                            return i\n            return None\n\n        st=[self.ROOT]\n        currentOrder=set()\n        while st[-1] not in currentOrder:\n            c=st[-1]\n            currentOrder.add(c)\n            nn=succeed(c,currentOrder)\n            if nn:\n                st.append(nn)\n        res=[i for i in st if i not in self.deathS]\n        return res\n        \n            \n            \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.isdead = False\n        self.children = []\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        p = Node('king')\n        self.root = p\n        self.dic = {kingName:p}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        p = Node(childName)\n        self.dic[childName] = p\n        parent = self.dic[parentName]\n        parent.children.append(p)\n\n    def death(self, name: str) -> None:\n        p = self.dic[name]\n        p.isdead = True \n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        \n        def dfs(n):\n            if n and not n.isdead:\n                ans.append(n.name)\n            for e in n.children:\n                dfs(e)\n        dfs(self.root)\n        # if ans: ans[0] = 'king'\n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        #what structure to use \n        #nested list, too hard to loop through?\n        #list with tuples? \n        #dictionary with each person being a key and part of an array value\n        #keep dictionary of dead people? \n        self.root = kingName\n        self.inheritance = {kingName: []}\n        self.dead = {}\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        #go through structure and add\n        if parentName in self.inheritance:\n            self.inheritance[parentName].append(childName)\n        self.inheritance[childName] = []\n            \n\n    def death(self, name: str) -> None:\n        #death doesn't affect successor function or current inheritance order\n        #go through structure and delete\n        self.dead[name] = 1\n\n    def getInheritanceOrder(self) -> List[str]:\n        #current order excluding dead people\n        arr = []\n        arr2 = []\n        self.helper(self.root, arr)\n        for person in arr:\n            if person in self.dead:\n                pass\n            else:\n                arr2.append(person)\n        return arr2\n\n    def helper(self, parent, arr):\n        if len(self.inheritance[parent]) == 0:\n            arr.append(parent)\n            return\n        arr.append(parent)\n        for child in self.inheritance[parent]:\n            self.helper(child, arr)\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.kids = []\n        self.dead = False\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.head = Node(kingName)\n        self.table = {}\n        self.table[kingName] = self.head\n    def birth(self, parentName: str, childName: str) -> None:\n        self.table[childName] = Node(childName)\n        self.table[parentName].kids.append(self.table[childName])\n        \n    def death(self, name: str) -> None:\n        self.table[name].dead = True\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        def helper(n):\n            if not n.dead:\n                ans.append(n.name)\n            for k in n.kids:\n                helper(k)\n        helper(self.head)\n        return ans\n            \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name: str):\n        self.name = name\n        self.children = []\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):        \n        self.root = Node(kingName)\n        self.n2n = {kingName:self.root}\n        self.dead = set()\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        node = Node(childName)\n        self.n2n[parentName].children.append(node)\n        self.n2n[childName] = node\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)        \n\n    def getInheritanceOrder(self) -> List[str]:\n        root = self.root\n        res = []\n        def dfs(root) -> None:\n            if root.name not in self.dead:\n                res.append(root.name)\n            for child in root.children:\n                dfs(child)\n        dfs(root)\n        return res\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.alive = {kingName: True}\n        self.children = {kingName: []}\n        self.order = [kingName]\n        self.kingName = kingName\n        self.placed = set([kingName])\n        self.parent = {}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.children[parentName].append(childName)\n        self.children[childName] = []\n        self.parent[childName] = parentName\n        self.alive[childName] = True\n\n    def death(self, name: str) -> None:\n        self.alive[name] = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        curr = self.kingName\n        while True:\n            curr = self.succ(curr)\n            if curr is None:\n                break\n            self.order.append(curr)\n            self.placed.add(curr)\n        ret = [o for o in self.order if self.alive[o]]\n        self.placed = set([self.kingName])\n        self.order = [self.kingName]\n        return ret\n        \n    def succ(self, x) -> str:\n        if not self.children[x] or all([c in self.placed for c in self.children[x]]):\n            if x == self.kingName:\n                return None\n            return self.succ(self.parent[x])\n        for c in self.children[x]:\n            if c not in self.placed:\n                return c\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class TreeNode:\n    \n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.alive = True\n\nclass ThroneInheritance:\n    mapping = {}\n    \n    def __init__(self, kingName: str):\n        self.mapping[kingName] = TreeNode(kingName)    \n        self.kingName = kingName\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        c = TreeNode(childName)\n        self.mapping[childName] = c\n        self.mapping[parentName].children.append(c)\n\n    def death(self, name: str) -> None:\n        self.mapping[name].alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        # Traverse the tree\n        ret = []\n        # print(\\\"?\\\")    \n        def dfs(node):\n            # print(node.name)\n            if node.alive:\n                ret.append(node.name)\n            for c in node.children:\n                dfs(c)\n    \n        dfs(self.mapping[self.kingName])\n        return ret\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import defaultdict\n\nclass ListNode:\n    def __init__(self, x, n=None):\n        self.val = x\n        self.next = n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.head = ListNode(kingName)\n        \n        self.d = defaultdict(list)\n        self.dead_people = {'king':0}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n#         looking = parentName\n#         while self.d[looking]:\n#             looking = self.d[looking][-1]\n        \n#         # insert child into list\n#         h = self.head\n#         prev = h\n#         while h != None:\n#             prev = h\n#             if h.val == looking:\n#                 break\n#             h = h.next\n#         t = prev.next\n#         prev.next = ListNode(childName, prev.next)\n            \n        self.d[parentName].append(childName)\n        self.dead_people[childName] = 0\n\n    def death(self, name: str) -> None:\n        self.dead_people[name] = 1\n        \n    def df(self, name):\n        \n        l = []\n        if self.dead_people[name] == 0:\n            l.append(name)\n        for childs in self.d[name]:\n            l = l + self.df(childs)\n            \n        return l\n        \n    def getInheritanceOrder(self) -> List[str]:\n        # ans = []\n        # h = self.head\n        # while h != None:\n        #     if self.dead_people[h.val] == 0:\n        #         ans.append(h.val)\n        #     h = h.next\n        # return ans\n        return self.df('king')\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.cache = {kingName:[]}\n        self.alive = {kingName:True}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.alive[childName] = True\n        if parentName not in self.cache:\n            self.cache[parentName] = []\n        self.cache[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.alive[name] = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        \n        def DFS(parent):\n            if self.alive[parent]:\n                order.append(parent)\n            if parent not in self.cache:\n                return\n            \n            for child in self.cache[parent]:\n                DFS(child)\n        \n        DFS(self.king)\n        return order\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name, is_king, parent):\n        self.name = name\n        self.is_king = is_king\n        self.parent = parent\n        self.children = []\n        self.is_dead = False\n\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.root = Node(kingName, True, None)\n        self.nmap = {kingName: self.root}\n        self.order_set = set()\n\n    def successor(self, x):\n        if not x.children or all(c in self.order_set for c in x.children):\n            if x.is_king: return None\n            return self.successor(x.parent)\n        else:\n            for c in x.children:\n                if c not in self.order_set: return c\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.nmap[parentName]\n        child = Node(childName, False, parent)\n        self.nmap[childName] = child\n        parent.children.append(child)\n\n    def death(self, name: str) -> None:\n        self.nmap[name].is_dead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = [self.root]\n        sc = self.successor(self.root)\n        while sc:\n            res.append(sc)\n            self.order_set.add(sc)\n            sc = self.successor(sc)\n        self.order_set = set()\n        return [n.name for n in res if not n.is_dead]\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Man:\n    def __init__(self, name, father):\n        self.name = name\n        self.father = father\n        self.children = []\n        self.alive = True\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.tree = Man(kingName, None)\n        self.names = {kingName: self.tree}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        father = self.names[parentName]\n        man = Man(childName, father)\n        father.children.append(man)\n        self.names[childName] = man\n\n    def death(self, name: str) -> None:\n        self.names[name].alive = False\n\n    def Succesor(self, man, curSet):\n        if not man.children or all([c.name in curSet for c in man.children]):\n            if man.father is None:\n                return None\n            else:\n                return self.Succesor(man.father, curSet)\n        else:\n            for c in man.children:\n                if c.name not in curSet:\n                    return c\n        return None\n\n    def getInheritanceOrder(self) -> List[str]:\n        curSet = set()\n        curList = []\n        if self.tree and self.tree.alive:\n            king = self.tree.name\n            curList.append(king)\n            curSet.add(king)\n        succesor = self.Succesor(self.tree, curSet)\n        while succesor:\n            if succesor.alive:\n                curList.append(succesor.name)\n            curSet.add(succesor.name)\n            succesor = self.Succesor(succesor, curSet)\n        return curList\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.family = OrderedDict()\n        self.family[kingName] = OrderedDict()\n        self.parentChildrenDictMap = dict()\n        self.parentChildrenDictMap[kingName] = self.family[kingName]\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        # import pprint\n        # pprint.pprint(self.family)\n        # pprint.pprint(self.parentChildrenDictMap)\n        if parentName not in self.parentChildrenDictMap:\n            raise Exception('No parent found')\n        children = self.parentChildrenDictMap[parentName]\n        if childName in children:\n            raise Exception('Child already exists')\n        children[childName] = OrderedDict()\n        self.parentChildrenDictMap[childName] = children[childName]\n                 \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        def dfs(root):\n            for parent, children in list(root.items()):\n                if parent not in self.dead:\n                    ans.append(parent)\n                dfs(root[parent])\n        dfs(self.family)\n        return ans\n            \n    \n    \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.res=['king']\n        self.ex={}\n        self.par={}\n        self.child={}\n\n    def birth(self, pN: str, cN: str) -> None:\n        self.child[cN]=pN\n        if pN in self.par:\n            # print(self.par)\n            self.par[pN].append(cN)\n        else:\n            self.par[pN]=deque([cN])\n        # print(self.par)\n\n    def death(self, name: str) -> None:\n        self.ex[name]=True\n\n    def getInheritanceOrder(self) -> List[str]:\n        final=[]\n        res=self.main()\n        for i in res:\n            if i not in self.ex:\n                final.append(i)\n        # self.res=final\n        return final\n        \n    def main(self):\n        # cP=self.par.deepcopy()\n        cC=self.child.copy()\n        cP=copy.deepcopy(self.par)\n        # print(cP, cC)\n        # cP={}\n        # for i in self.par:\n        #     cP[i]=self.par[i]\n        # print(cP)\n        \n        \n    \n        res=['king']\n        curr=res[-1]\n        \n        while(True):\n            if curr in cP and len(cP[curr])>0:\n                res.append(cP[curr][0])\n                cP[curr].popleft()\n                curr=res[-1]\n            else:\n                if curr not in cC:\n                    return res\n                curr=cC[curr]\n            if curr=='king' and len(cP[curr])==0:\n                # print(self.par, cP)\n                return res\n        \n        # return final\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import defaultdict\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.family = defaultdict(list)\n        self.dead = set()\n        self.parent = dict()\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.family[parentName].append(childName)\n        self.parent[childName] = parentName\n        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        order = [self.kingName]\n        \n        self.getInheritanceOrderFor(self.kingName, order)\n        \n        return [x for x in order if x not in self.dead]\n        \n    def getInheritanceOrderFor(self, name, order):\n        for child in self.family[name]:\n            order.append(child)\n            self.getInheritanceOrderFor(child, order)\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import defaultdict\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.dead = defaultdict(bool)\n        self.members = defaultdict(list)        \n        self.king = kingName\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.members[parentName].append(childName)\n        \n\n    def death(self, name: str) -> None:\n        self.dead[name] = True\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        inheritanceOrder = []\n        \n        def traverse(member):\n            if not self.dead[member]:\n                inheritanceOrder.append(member)\n            for child in self.members[member]:\n                traverse(child)\n\n        \n        traverse(self.king)\n        return inheritanceOrder\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.nation = defaultdict(list)\n        self.king = kingName\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.nation[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        result = []\n        def dfs(name):\n            if name not in self.dead:\n                result.append(name)\n            for child in self.nation[name]:\n                dfs(child)        \n        \n        dfs(self.king)\n        return result\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class TreeNode:\n    \n    def __init__(self, val):\n        self.val = val\n        self.children = []\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        \n        self.root = TreeNode(kingName)\n        self.mapping = collections.defaultdict()\n        self.mapping[kingName] = self.root\n        self.parent = collections.defaultdict()\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        self.mapping[parentName].children.append(childName)\n        self.mapping[childName] = TreeNode(childName)\n        self.parent[childName] = parentName\n        \n    def death(self, name: str) -> None:\n        \n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        def dfs(node):\n            res.append(node.val)\n            for child in node.children:\n                dfs(self.mapping[child])\n        dfs(self.root)\n        return [name for name in res if name not in self.dead]\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.alive = True\n    def dfs(self):\n        res = []\n        if self.alive:\n            res.append(self.name)\n        for child in self.children:\n            res.extend(child.dfs())\n        return res\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Person(kingName)\n        self.mapping = {}\n        self.mapping[kingName] = self.root\n\n    def birth(self, parentName: str, childName: str) -> None:\n        newOne = Person(childName)\n        parent = self.mapping[parentName]\n        self.mapping[childName] = newOne\n        parent.children.append(newOne)\n\n    def death(self, name: str) -> None:\n        self.mapping[name].alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        return self.root.dfs()\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name:str):\n        self.name = name\n        self.children = []\n        self.alive = True\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.lookup = {kingName:self.root}\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        p = self.lookup[parentName]\n        child = Node(childName)\n        p.children.append(child)\n        self.lookup[childName] = child\n\n    def death(self, name: str) -> None:\n        person = self.lookup[name]\n        person.alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        ret = []\n        def dfs(node:Node):\n            if node.alive:\n                ret.append(node.name)\n            for child in node.children:\n                dfs(child)\n        dfs(self.root)\n        return ret\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.childMap = dict([(kingName,[])])\n        self.parentMap = dict([])\n        self.grave = set([])\n    def birth(self, parentName: str, childName: str) -> None:\n        self.parentMap[childName] = parentName\n        if parentName in self.childMap:\n            self.childMap[parentName].append(childName)\n        else:\n            self.childMap[parentName] = [childName]\n\n    def death(self, name: str) -> None:\n        self.grave.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        curOrder = [self.kingName]\n        curOrderSet = set(curOrder)\n        n = self.successor(curOrder[-1],curOrder,curOrderSet)\n        while n:\n            curOrder.append(n)\n            curOrderSet.add(n)\n            n = self.successor(curOrder[-1],curOrder,curOrderSet)\n        \n        return [c for c in curOrder if c not in self.grave]\n        \n        \n    def successor(self, x, curOrder, curOrderSet):\n        if x in self.childMap:\n            for c in self.childMap[x]:\n                if c not in curOrderSet:\n                    return c\n        if x == self.kingName:\n            return None\n        return self.successor(self.parentMap[x], curOrder, curOrderSet)\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "import collections\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king=kingName\n        self.children = collections.defaultdict(list)\n        self.dead=collections.defaultdict(bool)\n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        self.children[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead[name]=True\n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        stack=[self.king]\n        ans=[]\n        while stack:\n            node=stack.pop()\n            if not self.dead[node]: ans.append(node)\n            for child in reversed(self.children[node]):\n                stack.append(child)\n\n        return ans", "class ThroneInheritance:\n    \n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.inherit = {}\n        self.inherit[kingName] = []\n        self.dead = {kingName:False}\n    \n    def birth(self, parentName: str, childName: str) -> None:\n        self.inherit[childName] = []\n        self.inherit[parentName].append(childName)\n        self.dead[childName] = False\n        return\n                \n    def death(self, name: str) -> None:\n        self.dead[name] = True\n\n\n    def getInheritanceOrder(self) -> List[str]:\n        return self.dfs(self.kingName)\n        \n    def dfs(self, name:str) -> List[str]:\n        ret = []\n        if not self.dead[name]:\n            ret.append(name)\n        for val in self.inherit[name]:\n            ret += self.dfs(val)\n        return ret\n    \n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.k = kingName\n        self.mp = defaultdict(list)\n        self.d = set()\n\n    def birth(self, p: str, c: str) -> None:\n        self.mp[p].append(c)\n\n    def death(self, name: str) -> None:\n        self.d.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        stk = [self.k]\n        while stk:\n            x = stk.pop(0)\n            if x not in self.d: ans.append(x)\n            stk = self.mp[x] + stk\n        return ans\n\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.dead = {}\n        self.mp = {}\n        self.mp[kingName] = []\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        if parentName not in self.mp:\n            self.mp[parentName] = []\n        self.mp[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead[name] = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        def dfs(self, res, node):\n            if node not in self.dead:\n                res.append(node)\n            if node not in self.mp:\n                return\n            for child in self.mp[node]:\n                dfs(self, res, child)\n        dfs(self, res, self.king)\n        return res\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.family_tree = collections.defaultdict(list)\n        self.king = kingName\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.family_tree[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        def dfs(name: str) -> None:\n            if name not in self.dead:\n                inheritance_order.append(name)\n            for kid in self.family_tree[name]:\n                dfs(kid)\n\n        inheritance_order = []\n        dfs(self.king)\n        return inheritance_order", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = kingName\n        self.dict = defaultdict(list)\n        self.dead = set()\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.dict[parentName].append(childName)\n        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        return self.dfs(self.root, [])\n    \n    \n    def dfs(self, root, arr):\n        # preorder\n        if root not in self.dead:\n            arr.append(root)\n        if root in self.dict:\n            for kid in self.dict[root]:\n                self.dfs(kid, arr)\n        return arr\n        \n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.G = collections.defaultdict(list)\n        self.dead = set()\n        self.king = kingName\n    def birth(self, parentName: str, childName: str) -> None:\n        self.G[parentName].append(childName)\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        def dfs(node, ans):\n            if node not in self.dead: \n                ans.append(node)\n            for nei in self.G[node]:\n                dfs(nei, ans)\n        dfs(self.king, ans)\n        return ans\n        \n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.family = {}\n        self.family[kingName] =[]\n        self.dead = set([])\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.family[parentName].append(childName)\n        self.family[childName] = []\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        def dfs (name):\n            if name not in self.dead:\n                    order.append(name)    \n            for child in self.family[name]:\n                dfs(child)\n        dfs(self.king)\n        return order\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.graph = collections.defaultdict(lambda: [])\n        self.dead = set()\n        self.king = kingName\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.graph[parentName].append(childName)\n        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        def dfs(root):\n            if not root:\n                return \n            if root not in self.dead:\n                ans.append(root)\n            for child in self.graph[root]:\n                dfs(child)\n        dfs(self.king)\n        return ans\n            \n            \n            \n            \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king_name = kingName\n        self.parents = collections.defaultdict(list)\n        self.deads = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.parents[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.deads.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        def dfs(name: str):\n            if name not in self.deads:\n                res.append(name)\n            for child in self.parents[name]:\n                dfs(child)\n        dfs(self.king_name)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.tree = collections.defaultdict(list)\n        self.tree[kingName] = []\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.tree[parentName].append(childName)\n        \n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        def dfs(name):\n            res.append(name)\n            for child in self.tree[name]:\n                dfs(child)\n        dfs(self.king)\n        return [name for name in res if name not in self.dead]\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.data = {kingName: list()}\n        self.dead = set()\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        self.data[parentName].append(childName)\n        self.data[childName] = list()\n\n\n    def death(self, name: str) -> None:\n        \n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        out, seen = [], set()\n        \n        def _helper(person) -> None:\n            if person not in seen:\n                if person not in self.dead:\n                    out.append(person)\n            for child in self.data[person]:\n                _helper(child)\n                \n        _helper(self.king)\n        return out\n        \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.nation = collections.defaultdict(list)\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.nation[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        self.ans = []\n        self.dfs(self.king)\n        return self.ans\n    \n    def dfs(self, cur):\n        if cur not in self.dead:\n            self.ans.append(cur)\n        for child in self.nation[cur]:\n            self.dfs(child)\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.personDict = defaultdict(list)\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.personDict[parentName].append(childName)        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        self.ans=[]\n        self.dfs(self.kingName)\n        return self.ans\n        \n    def dfs(self,name: str):\n        if name not in self.dead:\n            self.ans.append(name)\n        for childName in self.personDict[name]:\n            self.dfs(childName)\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import defaultdict\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = kingName\n        self.d = defaultdict(list)\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.d[parentName].append(childName)\n        return\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        return \n    \n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        def p(root):\n            nonlocal ans\n            if root not in self.dead:\n                ans.append(root)\n            \n            for i in self.d[root]:\n                p(i)\n        p(self.root)\n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import defaultdict\n\nclass ThroneInheritance:\n    # inheritance = []\n    def __init__(self, kingName: str):\n        self.family = defaultdict(list)\n        self.king = kingName\n        self.dead = set()\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.family[parentName].append(childName)\n        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        self.ans = []\n        self.dfs(self.king)\n        return self.ans\n    \n    def dfs(self, root):\n        if root not in self.dead:\n            self.ans.append(root)\n        \n        for child in self.family[root]:\n            self.dfs(child)\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import OrderedDict, defaultdict\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.parent2son = {}\n        self.parent2son[kingName] = OrderedDict()\n        self.son2parent = {}\n        self.deadset = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.son2parent[childName] = parentName\n        if parentName not in self.parent2son:\n            self.parent2son[parentName] = OrderedDict()\n        self.parent2son[parentName][childName] = 0\n        \n\n    def death(self, name: str) -> None:\n        self.deadset.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        stack = [self.kingName]\n        while stack:\n            name = stack.pop()\n            if name in self.parent2son:\n                next = []\n                for son in self.parent2son[name]:\n                    next.insert(0, son)\n                stack = stack + next\n            if name not in self.deadset:\n                order.append(name)\n        return order\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = kingName\n        self.child_list = {\n            self.root: []\n        }\n        self.death_dict = {}\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.child_list[parentName].append(childName)\n        self.child_list[childName] = []\n        \n\n    def death(self, name: str) -> None:\n        self.death_dict[name] = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        answer_list = []\n        def _dfs(cur_node):\n            if cur_node not in self.death_dict:\n                answer_list.append(cur_node)\n            for child in self.child_list[cur_node]:\n                _dfs(child)\n        _dfs(self.root)\n        return answer_list\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        \n        self.root = kingName\n        self.alive = {}\n        self.alive[kingName] = 0\n        self.edges = {self.root:[]}\n    def birth(self, parentName: str, childName: str) -> None:\n        self.alive[childName] = self.alive[parentName]+1\n        \n        if parentName in self.edges:\n            self.edges[parentName].append(childName)\n            if childName not in self.edges:\n                self.edges[childName] = []\n        else:\n            if childName not in self.edges:\n                self.edges[childName] = []\n            self.edges[parentName] = [childName]\n            \n   \n    def death(self, name: str) -> None:\n        del self.alive[name]\n        \n    def getInheritanceOrder(self) -> List[str]:\n        \n        hierarchy = []\n        def dfs(cur,parent=-1):\n            nonlocal hierarchy\n            if cur in self.alive:\n                hierarchy.append(cur)\n            for i in self.edges[cur]:\n                if i!=parent:\n                    dfs(i,cur)\n        dfs(self.root)\n        return hierarchy\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, king: str):\n        self.king = king\n        # par -> children\n        self.g = defaultdict(list)\n        self.dead = set()\n\n    def birth(self, parent: str, child: str) -> None:\n        self.g[parent].append(child)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        curOrder = []\n        \n        def recurse(u):\n            \n            curOrder.append(u)\n            \n            for v in self.g[u]:\n                recurse(v)\n            \n        recurse(self.king)\n            \n        return [u for u in curOrder if u not in self.dead]\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.nameBook = {}\n        self.nameBook[kingName] = (kingName, [])\n        self.king = self.nameBook[kingName]\n        \n        self.deathBook = set()\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        if parentName in self.nameBook:\n            self.nameBook[childName] = (childName, [])\n            self.nameBook[parentName][1].append(self.nameBook[childName])\n        \n\n    def death(self, name: str) -> None:\n        \n        self.deathBook.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        InheritOrder = []\n        stack = [self.king]\n        while stack:\n            name, children = stack.pop()\n            \n            if name not in self.deathBook:\n                InheritOrder.append(name)\n            \n            stack.extend(children[::-1])\n            \n            \n            \n\n        return InheritOrder\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n    from collections import deque\n\n    def __init__(self, kingName: str):\n        self.kingName=kingName\n        self.dic={kingName:[1,[]]}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.dic[parentName][1].append(childName)\n        self.dic[childName]=[1,[]]\n\n    def death(self, name: str) -> None:\n        self.dic[name][0]=0\n\n    def getInheritanceOrder(self) -> List[str]:\n        d=deque([self.kingName])\n        ans=[]\n        while len(d)>0:\n            name=d.pop()\n            if self.dic[name][0]:\n                ans.append(name)\n            listt=self.dic[name][1]\n            for i in range(len(listt)):\n                d.append(listt[-i-1])\n            \n        return ans", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.G = collections.defaultdict(list)\n        self.dead = set()\n        self.king = kingName\n        self.parent = dict()\n    def birth(self, parentName: str, childName: str) -> None:\n        self.G[parentName].append(childName)\n        self.parent[childName] = parentName\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        toVisit = collections.defaultdict(int)\n        visited = set()\n        ans = []\n        def dfs(node, ans):\n            if node not in self.dead: \n                ans.append(node)\n            for nei in self.G[node]:\n                dfs(nei, ans)\n        dfs(self.king, ans)\n        return ans\n        \n        \\\"\\\"\\\"         \nSuccessor(x, curOrder):\n    if x has no children or all of x's children are in curOrder:\n        if x is the king return null\n        else return Successor(x's parent, curOrder)\n    else return x's oldest child who's not in curOrder\n\\\"\\\"\\\"\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.nation = defaultdict(list)\n        self.king = kingName\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.nation[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        self.ans = []\n        self.dfs(self.king)\n        return self.ans\n    \n    def dfs(self, cur):\n        if cur not in self.dead:\n            self.ans.append(cur)\n        for child in self.nation[cur]:\n            self.dfs(child)\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.alive = True\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.people = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.people[parentName].children.append(child)\n        self.people[childName] = child\n\n    def death(self, name: str) -> None:\n        self.people[name].alive = False\n        \n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        self.helper(self.root, res)\n        return res\n        \n    def helper(self, root, res):\n        if root.alive:\n            res.append(root.name)\n        if not root.children:\n            return\n        for child in root.children:\n            self.helper(child, res)\n        \n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    def __init__(self, name):\n        self.name = name\n        self.alive = True\n        self.children = []\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = Person(kingName)\n        self.name_person_map = {kingName: self.king}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.name_person_map[parentName]\n        child = Person(childName)\n        parent.children.append(child)\n        self.name_person_map[childName] = child\n\n    def death(self, name: str) -> None:\n        person = self.name_person_map[name]\n        person.alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        self.preorder_dfs(self.king, res)\n        return res\n    \n    def preorder_dfs(self, person, res):\n        if person.alive:\n            res.append(person.name)\n        for child in person.children:\n            self.preorder_dfs(child, res)\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    \n    def __init__(self, name: str) -> None:\n        self.name = name\n        self.children: List[\\\"Person\\\"] = list()\n        self.alive = True\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.head: Person = Person(kingName)\n        self.data = {kingName: self.head}\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        current = Person(childName)\n        self.data[parentName].children.append(current)\n        self.data[childName] = current\n\n\n    def death(self, name: str) -> None:\n        \n        self.data[name].alive = False\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        seen, out = set(), []\n        \n        def _helper(node):\n            if node not in seen:\n                seen.add(node)\n                if node.alive:\n                    out.append(node.name)\n                    \n            for child in node.children:\n                _helper(child)\n                \n        _helper(self.head)\n        return out\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class Member:\n    def __init__(self, name):\n        self.name = name\n        self.dead = False\n        self.children = []\n    \n\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.dummy = Member('')\n        self.root = Member(kingName)\n        self.dummy.children.append(self.root)\n        self.member_table = {'king': self.root}\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.member_table[parentName]\n        child = Member(childName)\n        parent.children.append(child)\n        self.member_table[childName] = child\n\n    def death(self, name: str) -> None:\n        self.member_table[name].dead = True\n\n    \n    def getInheritanceOrder(self) -> List[str]:\n        def dfs(root, inheritance_order):\n            for child in root.children:\n                if not child.dead:\n                    inheritance_order.append(child.name)\n                dfs(child, inheritance_order)\n            return\n        \n        \n        inheritance_order = []\n        dfs(self.dummy, inheritance_order)\n        return inheritance_order\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class TreeNode:\n\n    def __init__(self, name: str):\n        self.name = name\n        self.is_alive = True\n        self.children = []\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = TreeNode(kingName)\n        self.nodes = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = TreeNode(childName)\n        self.nodes[parentName].children.append(child)\n        self.nodes[childName] = child\n\n    def death(self, name: str) -> None:\n        self.nodes[name].is_alive = False\n\n    def getInheritanceOrder(self):\n        \\\"\\\"\\\"\n        This method derives the\n\n        :return: Array of names by inheritance order\n        :rtype: list[str]\n        \\\"\\\"\\\"\n        def recursive(head: TreeNode, inherit):\n            if head.is_alive:\n                inherit.append(head.name)\n            for child in head.children:\n                inherit = recursive(child, inherit)\n            return inherit\n\n        return recursive(self.root, [])\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.alive = {kingName: True}\n        self.children = {kingName: []}\n        self.parent = {kingName: None}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.alive[childName] = True\n        self.children[childName] = []\n        self.children[parentName].append(childName)\n        self.parent[childName] = parentName\n\n    def death(self, name: str) -> None:\n        self.alive[name] = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        if self.alive[self.king]:\n            ans.append(self.king)\n        cur = self.king\n        index = [0]\n        while cur:\n            if len(self.children[cur]) > index[-1]:\n                cur = self.children[cur][index[-1]]\n                index[-1] += 1\n                index.append(0)\n                if self.alive[cur]:\n                    ans.append(cur)\n            else:\n                cur = self.parent[cur]\n                index.pop()\n        return ans\n            \n        \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.tree = {kingName: [True, []]}    # dict-tree, key--name, value--(alive, child_keys)\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = [True, []]\n        self.tree[childName] = child\n        self.tree[parentName][1].append(childName)\n        \n\n    def death(self, name: str) -> None:\n        self.tree[name][0] = False\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        result = []\n        def dfs(root_name):\n            result.append(root_name)\n            if self.tree[root_name][1]:\n                for child in self.tree[root_name][1]:\n                    dfs(child)\n        dfs(self.king)\n        return [x for x in result if self.tree[x][0]]\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node(object):\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.isDead = False\n        \n    def addChild(self, child):\n        self.children.append(child)\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.d = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.d[parentName].addChild(child)\n        self.d[childName] = child\n            \n    def death(self, name: str) -> None:\n        self.d[name].isDead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        def dfs(root):\n            if not root:\n                return\n            if not root.isDead:\n                order.append(root.name)\n            for c in root.children:\n                dfs(c)\n        dfs(self.root)        \n        return order\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    def __init__(self, name):\n        self.children = []\n        self.name = name\n        self.isAlive = True\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Person(kingName)\n        self.persons = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        if parentName not in self.persons:\n            return\n        else:\n            newChild = Person(childName)\n            self.persons[parentName].children.append(newChild)\n            self.persons[childName] = newChild\n            \n    def death(self, name: str) -> None:\n        self.persons[name].isAlive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        \n        def dfs(person):\n            stack = [person]\n            while(len(stack)>0):\n                current = stack.pop()\n                if current.isAlive:\n                    ans.append(current.name)\n                for child in current.children[::-1]:\n                    stack.append(child)\n        \n        dfs(self.root)\n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Tree:\n    \n    def __init__(self, name):\n        \\\"\\\"\\\"\n        name: name of the current tree\n        child: list of children trees\n        \\\"\\\"\\\"\n        self.name = name\n        self.child = []\n        self.alive = True\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.heritance = Tree(kingName)\n        self.dict = {kingName: self.heritance}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.dict[parentName]\n        child = Tree(childName)\n        parent.child.append(child)\n        self.dict[childName] = child\n\n    def death(self, name: str) -> None:\n        self.dict[name].alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        # would be a dfs of the whole tree\n        # without the name of dead person\n        order = []\n        child = [self.heritance]\n        while child:\n            c = child.pop()\n            if c.alive:\n                order.append(c.name)\n            for subchild in c.child[::-1]:\n                child.append(subchild)\n        \n        return order\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName=kingName\n        self.relation={kingName:[]}\n        self.dead={}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        if parentName in self.relation:\n            self.relation[parentName].append(childName)\n        else:\n            self.relation[parentName]=[childName]\n            \n        \n        \n\n    def death(self, name: str) -> None:\n        self.dead[name]=True\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        res=[]\n        self.dfs(self.kingName,res)\n        return res\n    \n    def dfs(self,name,out):\n        if name not in self.dead:\n            out.append(name)\n        if name not in self.relation:\n            return\n        for c in self.relation[name]:\n            self.dfs(c,out)\n        return\n            \n            \n    \n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "#1600\nclass Person:\n    def __init__(self,name):\n        self.name = name\n        self.children = []\n        self.alive = True\n    def birth(self,name):\n        self.children.append(Person(name))\n        return self.children[-1]\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.king = Person(kingName)\n        self.dic = {kingName: self.king}\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.dic[parentName]\n        child = parent.birth(childName)\n        self.dic[childName] = child\n    def death(self, name: str) -> None:\n        self.dic[name].alive = False\n    def getInheritanceOrder(self) -> 'List[str]':\n        res = []\n        stack = [self.king]\n        while stack:\n            p = stack.pop()\n            if p.alive:\n                res.append(p.name)\n            for child in p.children[::-1]:\n                stack.append(child)\n        return res", "class Node(object):\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.isDead = False\n        \n    def addChild(self, child):\n        self.children.append(child)\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.node = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.node[parentName].addChild(child)\n        self.node[childName] = child\n            \n    def death(self, name: str) -> None:\n        self.node[name].isDead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        def dfs(root):\n            if not root:\n                return\n            if not root.isDead:\n                order.append(root.name)\n            for c in root.children:\n                dfs(c)\n        dfs(self.root)        \n        return order\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class TreeNode:\n\n    def __init__(self, name: str):\n        self.name = name\n        self.is_alive = True\n        self.children = []\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = TreeNode(kingName)\n        self.nodes = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = TreeNode(childName)\n        self.nodes[parentName].children.append(child)\n        self.nodes[childName] = child\n\n    def death(self, name: str) -> None:\n        self.nodes[name].is_alive = False\n\n    def getInheritanceOrder(self):\n        \\\"\\\"\\\"\n\n        :return: Array of names by inheritance order\n        :rtype: list[str]\n        \\\"\\\"\\\"\n        def recursive(head: TreeNode):\n            if head.is_alive:\n                inherit = [head.name]\n            else:\n                inherit = []\n            for child in head.children:\n                inherit = inherit + recursive(child)\n            return inherit\n\n        return recursive(self.root)\n", "class Person:\n    def __init__(self, name: str, parent):\n        self.name = name\n        self.parent = parent\n        self.alive = True\n        self.children = []\n    \n    def add_kid(self, kid):\n        self.children.append(kid)\n    \n    def kill(self):\n        self.alive = False\n\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.king = Person(kingName, None)\n        self.person_dict = {kingName: self.king}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.person_dict[parentName]\n        new_kid = Person(childName, parentName)\n        self.person_dict[childName] = new_kid\n        parent.add_kid(new_kid)\n\n    def death(self, name: str) -> None:\n        person = self.person_dict[name]\n        person.kill()\n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        stack = [self.king]\n        while stack:\n            person = stack.pop()\n            if person.alive:\n                ans.append(person.name)\n            if person.children:\n                stack.extend(person.children[::-1])\n        return ans\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king_name =kingName\n        self.inheritance_tree = {\n            kingName:{\n                \\\"children\\\":[],\n                \\\"death\\\" : False\n            },\n            \n        }\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.inheritance_tree[parentName][\\\"children\\\"].append(childName)\n        self.inheritance_tree[childName] = {\n                \\\"children\\\":[],\n                \\\"death\\\" : False\n        }\n\n    def death(self, name: str) -> None:\n        self.inheritance_tree[name][\\\"death\\\"] = True\n        \n\n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        res = []\n        def helper(person,res):\n            # print(self.inheritance_tree[person][\\\"children\\\"])\n            if self.inheritance_tree[person][\\\"death\\\"] == False:\n                res.append(person)\n\n            if len(self.inheritance_tree[person]) == 0:\n                return \n\n            for child in self.inheritance_tree[person][\\\"children\\\"]:\n                helper(child,res)\n        \n        helper(self.king_name, res)\n\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class Node:\n    def __init__(self, name: str):\n        self.name = name\n        self.children = []\n        self.is_dead = False\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = kingName\n        self.nodes = {kingName: Node(kingName)}\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.nodes[parentName].children.append(child)\n        self.nodes.update({childName:child})\n            \n\n    def death(self, name: str) -> None:\n        self.nodes[name].is_dead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        result = []\n        seq = [self.nodes[self.root]]\n        while seq:\n            one = seq.pop()\n            if not one.is_dead:\n                result.append(one.name)\n            if one.children:\n                seq.extend(one.children[::-1])\n            \n        return result\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class TreeNode:\n\n    def __init__(self, name: str):\n        self.name = name\n        self.is_alive = True\n        self.children = []\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = TreeNode(kingName)\n        self.nodes = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = TreeNode(childName)\n        self.nodes[parentName].children.append(child)\n        self.nodes[childName] = child\n\n    def death(self, name: str) -> None:\n        self.nodes[name].is_alive = False\n\n    def getInheritanceOrder(self):\n        \\\"\\\"\\\"\n\n        :return: Array of names by inheritance order\n        :rtype: list[str]\n        \\\"\\\"\\\"\n        def recursive(head: TreeNode):\n            if head is None:\n                return []\n            if head.is_alive:\n                inherit = [head.name]\n            else:\n                inherit = []\n            for child in head.children:\n                inherit = inherit + recursive(child)\n            return inherit\n\n        return recursive(self.root)\n", "class ThroneInheritance:\n    \n    class Person:\n        \n        def __init__(self,name, parent = None):\n            self.parent = parent\n            self.name = name\n            self.children = []\n            self.isAlive = True\n    \n\n    def __init__(self, kingName: str):\n        self.h = {kingName: self.Person(kingName)}\n        self.cur_king = kingName\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.h[childName] = self.Person(childName, parentName)\n        self.h[parentName].children.append(self.h[childName])\n        \n\n    def death(self, name: str) -> None:\n        self.h[name].isAlive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        stack = [self.h[self.cur_king]]\n        while len(stack):\n            node = stack[-1]\n            stack.pop()\n            if node.isAlive:\n                res.append(node.name)\n            for i in range(len(node.children)):\n                stack.append(node.children[-1-i])\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "import collections\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        self.mapping = collections.defaultdict(list)\n        self.deads = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.mapping[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.deads.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        self.get_order(res, self.kingName)\n        return res\n    \n    def get_order(self, res, parent):\n        \n        if parent not in self.deads:\n            res.append(parent)\n        \n        for child in self.mapping[parent]:\n            self.get_order(res, child)\n        \n        \n    \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.result = defaultdict(list)\n        self.king = kingName\n        self.dead = set()\n    \n    def successor(self, x):\n        if x not in self.dead:\n            self.order.append(x)\n        for i in self.result[x]:\n            self.successor(i)\n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        self.result[parentName].append(childName)\n\n\n    def death(self, name: str) -> None:\n\n        self.dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        self.order = []\n        name = self.king\n        self.successor(name)\n        return self.order\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Member:\n    \n    def __init__(self, name):\n        self.name = name\n        self.alive = True\n        self.nextChild = None\n        self.nextSibling = None\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.members = {}\n        self.king = Member(kingName)\n        self.members[kingName] = self.king\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.members[parentName]\n        \n        child = Member(childName)\n        self.members[childName] = child\n        \n        if parent.nextChild is None:\n            parent.nextChild = child\n            return\n        member = parent.nextChild\n        while member.nextSibling:\n            member = member.nextSibling\n        member.nextSibling = child\n        \n\n    def death(self, name: str) -> None:\n        self.members[name].alive = False\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        inheritanceOrder = []\n        \n        def traverseInOrder(member):\n            if member is None:\n                return\n            \n            if member.alive:\n                inheritanceOrder.append(member.name)\n            traverseInOrder(member.nextChild)\n            traverseInOrder(member.nextSibling)\n        \n        traverseInOrder(self.king)\n        return inheritanceOrder\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node(object):\n    def __init__(self):\n        self.children = []\n        self.name = ''\n        self.dead = False\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self._root = Node()\n        self._root.name = kingName\n        self._locator = {kingName: self._root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node()\n        child.name = childName\n        self._locator[childName] = child\n        self._locator[parentName].children.append(child)\n\n    def death(self, name: str) -> None:\n        self._locator[name].dead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        stack = []\n        order = []\n        current = self._root\n        \n        while True:\n            if current:\n                if not current.dead:\n                    order.append(current.name)\n                stack.extend(current.children[::-1])\n                current = None\n            elif len(stack) > 0:\n                current, stack = stack[-1], stack[:-1]\n            else:\n                break\n        return order\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.isAlive = True\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = Node(kingName)\n        self.dict = {kingName: self.king}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        new_node = Node(childName)\n        self.dict[parentName].children.append(new_node)\n        self.dict[childName] = new_node\n\n    def death(self, name: str) -> None:\n        self.dict[name].isAlive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        ordering = []\n\n        def preOrder(node):\n            if node.isAlive:\n                ordering.append(node.name)\n            for c in node.children:\n                preOrder(c)\n            \n        preOrder(self.king)\n        return ordering\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name \n        self.alive = True\n        self.childs = []\n\n    def addChild(self, child):\n        self.childs.append(child)\n\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.king = Node(kingName)\n        self.d = {kingName: self.king}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.d[childName] = Node(childName)\n        self.d[parentName].addChild(self.d[childName])\n        \n    def death(self, name: str) -> None:\n        self.d[name].alive = False \n\n    def getInheritanceOrder(self) -> List[str]:\n        def dfs(node):\n            ans = [node.name]*node.alive\n            for x in node.childs:\n                ans.extend(dfs(x))\n            return ans \n        \n        return dfs(self.king)    \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node(object):\n    def __init__(self, name, parent=None):\n        self.name = name\n        self.parent = parent\n        self.children = []\n        \n    def addChild(self, child):\n        self.children.append(child)\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.node = {kingName: self.root}\n        self.deaths = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.node[parentName]\n        child = Node(childName, parent)\n        parent.addChild(child)\n        self.node[childName] = child\n            \n    def death(self, name: str) -> None:\n        self.deaths.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        def dfs(root):\n            if not root:\n                return\n            if root.name not in self.deaths:\n                order.append(root.name)\n            for c in root.children:\n                dfs(c)\n        dfs(self.root)        \n        return order\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node(object):\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        \n    def addChild(self, child):\n        self.children.append(child)\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.node = {kingName: self.root}\n        self.deaths = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.node[parentName].addChild(child)\n        self.node[childName] = child\n            \n    def death(self, name: str) -> None:\n        self.deaths.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        def dfs(root):\n            if not root:\n                return\n            if root.name not in self.deaths:\n                order.append(root.name)\n            for c in root.children:\n                dfs(c)\n        dfs(self.root)        \n        return order\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class node:\n    def __init__(self, name):\n        self.name = name\n        self.isdead = False\n\nfrom collections import defaultdict\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingName = kingName\n        n = node(kingName)\n        \n        self.nodes = {}\n        self.nodes[kingName] = n\n        \n        self.child = defaultdict(list)\n        self.child[n]=[]\n    \n    def dfs(self, node):\n        #print(node)\n        val = [node.name] if node.isdead==False else []\n        for c in self.child[node]:\n            c = self.nodes[c]\n            n = self.dfs(c)\n            val.extend(n)\n            \n        return val\n    \n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.nodes[parentName]\n        child = node(childName)\n        self.nodes[childName] = child\n        \n        self.child[parent].append(childName)\n\n    def death(self, name: str) -> None:\n        n = self.nodes[name]\n        n.isdead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        n = self.nodes[self.kingName]\n        return self.dfs(n)\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n\n  def __init__(self, name):\n    self.name = name\n    self.children = []\n    pass\n\n  def give_birth_to(self, node):\n    self.children.append(node)\n    return\n\n\nclass ThroneInheritance:\n\n  def __init__(self, kingName: str):\n    self.name_directory = dict()\n    self.root = Node(kingName)\n    self.name_directory[kingName] = self.root\n    pass\n\n  def birth(self, parentName: str, childName: str) -> None:\n    child_node = Node(childName)\n    self.name_directory[childName] = child_node\n    parent_node = self.name_directory[parentName]\n    parent_node.give_birth_to(child_node)\n    pass\n\n  def death(self, name: str) -> None:\n    del self.name_directory[name]\n    pass\n\n  def getInheritanceOrder(self) -> List[str]:\n    result = []\n\n    def logic(node: Node, result: List[str]):\n      if node == None:\n        return\n\n      if node.name in self.name_directory:\n        result.append(node.name)\n\n      for child in node.children:\n        logic(child, result)\n        pass\n\n      return\n\n    logic(self.root, result)\n    return result\n", "class ThroneInheritance:\n    class FamilyMember:       \n        def __init__(self, name: str):\n            self.name = name\n            self.children = []\n            self.is_alive = True\n        \n        def newChild(self, name: str):\n            child = ThroneInheritance.FamilyMember(name)\n            self.children.append(child)\n            return child\n        \n        def kill(self):\n            self.is_alive = False\n        \n    king = None\n    family = {}\n    inheritenceOrder = []\n    def __init__(self, kingName: str):\n        self.king = self.FamilyMember(kingName)\n        self.family[kingName] = self.king\n    \n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = self.family[parentName].newChild(childName)\n        self.family[childName] = child\n\n    def death(self, name: str) -> None:\n        self.family[name].kill()\n\n    def buildInheritanceOrder(self, root: FamilyMember):\n        if not root:\n            return\n        if root.is_alive:\n            self.inheritenceOrder.append(root.name)\n        for child in root.children:\n            self.buildInheritanceOrder(child)\n        return   \n        \n    def getInheritanceOrder(self) -> List[str]:\n        self.inheritenceOrder = []\n        self.buildInheritanceOrder(self.king)\n        return self.inheritenceOrder\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    \n    def __init__(self, name: str) -> None:\n        self.name = name\n        self.children: List[\\\"Person\\\"] = list()\n        self.alive = True\n        self.next = self.prev = None\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.head: Person = Person(kingName)\n        self.data = {kingName: self.head}\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        current = Person(childName)\n        prev = self.data[parentName]\n        while prev.children:\n            prev = prev.children[-1]\n            \n        if prev.next is not None:\n            next = prev.next\n            prev.next, current.prev = current, prev\n            current.next, next.prev = next, current\n        else:\n            prev.next, current.prev = current, prev\n                \n        self.data[parentName].children.append(current)\n        self.data[childName] = current\n\n\n    def death(self, name: str) -> None:\n        \n        self.data[name].alive = False\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        current, out = self.head, []\n        while current is not None:\n            if current.alive:\n                out.append(current.name)\n            current = current.next\n        return out\n        \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "from collections import OrderedDict\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        # Maintain a tree\n        self._kingName = kingName\n        self._family = { kingName: [] }\n        self._dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self._family[parentName].append(childName)\n        self._family[childName] = []\n\n\n    def death(self, name: str) -> None:\n        self._dead.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        self._order(self._kingName, order)\n        return order\n\n    \n    def _order(self, name, order):\n        if name not in self._dead: order.append(name)\n        for child in self._family[name]:\n            self._order(child, order)\n            \n\n        \n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    \n    def __init__(self, name: str) -> None:\n        self.name = name\n        self.children: List[\\\"Person\\\"] = list()\n        self.alive = True\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.head: Person = Person(kingName)\n        self.data = {kingName: self.head}\n        self.memo = (0, [])\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        current = Person(childName)\n        self.data[parentName].children.append(current)\n        self.data[childName] = current\n\n\n    def death(self, name: str) -> None:\n        \n        self.data[name].alive = False\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        horizon, seen, out = [(self.head, iter(self.head.children))], set(), []\n        while horizon:\n            current, children_iter = horizon[-1]\n            if current not in seen:\n                seen.add(current)\n                if current.alive:\n                    out.append(current.name)\n            try:\n                child = next(children_iter)\n            except StopIteration:\n                horizon.pop()\n                continue\n            else:\n                horizon.append((child, iter(child.children)))\n                \n        return out\n        \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingname=kingName\n        self.dead=set()\n        self.m=collections.defaultdict(list)\n        self.m[kingName]=[]\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.m[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n        \n    def getorderhelper(self,name,order):\n        if name not in self.dead:\n            order.append(name)        \n        for n in self.m[name]:\n            self.getorderhelper(n,order)\n    def getInheritanceOrder(self) -> List[str]:\n        order=[]\n        self.getorderhelper(self.kingname,order)\n        return order\n        \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.tree = {kingName:[True, []]}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.tree[parentName][1].append(childName)\n        self.tree[childName] = [True, []]\n        \n\n    def death(self, name: str) -> None:\n        self.tree[name][0] = False\n        \n    def dfs(self, name):\n        if self.tree[name][0]:\n            yield name\n        for child in self.tree[name][1]:\n            yield from self.dfs(child)\n        \n    \n    def getInheritanceOrder(self) -> List[str]:        \n        return list(self.dfs(self.king))\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    class Person:\n        def __init__(self, name):\n            self.name = name\n            self.children = list()\n            self.is_alive = True\n\n    \n    def __init__(self, kingName: str):\n        self.root = ThroneInheritance.Person(kingName)\n        self.tracker = {kingName: self.root}\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        if parentName not in self.tracker:\n            return\n        self.tracker[parentName].children.append(ThroneInheritance.Person(childName))\n        self.tracker[childName] = self.tracker[parentName].children[-1]\n\n    def death(self, name: str) -> None:\n        self.tracker[name].is_alive = False\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        res = list()\n        \n        def recursion(node):\n            if node.is_alive:\n                res.append(node.name)\n            for child in node.children:\n                recursion(child)\n        recursion(self.root)\n        return res\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class people:\n    def __init__(self, name, dead = False, child = None):\n        self.name = name\n        self.dead = dead\n        self.child = []\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        king = people(kingName)\n        self.hash = {kingName: king}\n        self.king = king\n\n    def birth(self, parentName: str, childName: str) -> None:\n        pp = people(childName)\n        self.hash[parentName].child.append(pp)\n        self.hash[childName] = pp\n\n    def death(self, name: str) -> None:\n        self.hash[name].dead = True\n\n    def getInheritanceOrder(self):\n        self.res = []\n        def dfs(pp):\n            print((pp.name))\n            if not pp.dead:\n                self.res.append(pp.name)\n            for v in pp.child:\n                dfs(v)\n            \n        dfs(self.king)\n        return self.res\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    def __init__(self, name):\n        self.name = name\n        self.alive = True\n        self.children = []\n    \n    def preOrder(self, output):\n        if self.alive:\n            output.append(self.name)\n        \n        for child in self.children:\n            child.preOrder(output)\n\nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.root = Person(kingName)\n        self.people = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Person(childName)\n        self.people[parentName].children.append(child)\n        self.people[childName] = child\n\n    def death(self, name: str) -> None:\n        self.people[name].alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        ret = []\n        self.root.preOrder(ret)\n        return ret\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class King:\n    def __init__(self, name):\n        self.name = name\n        self.children = dict()\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = King(kingName)\n        self.inheritTree = collections.defaultdict(King)\n        self.inheritTree[kingName] = self.king\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        tree = self.inheritTree\n        parentNode = tree[parentName]\n        childNode = King(childName)\n        parentNode.children[childName] = childNode\n        tree[childName] = childNode\n        \n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        tree = self.inheritTree\n        res = []\n        \n        def inorder(king, res):\n            if king not in self.dead:\n                res.append(king)\n            child = tree[king]\n            for c in child.children:\n                inorder(c, res)\n        \n        king = self.king\n        inorder(king.name, res)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, val, childs=None):\n        self.val, self.childs = val, childs if childs else []\n        \nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.name2node = {kingName: self.root}\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        par = self.name2node[parentName]\n        node = Node(childName)\n        par.childs.append(node)\n        self.name2node[childName] = node\n\n    def death(self, name: str) -> None:\n        self.dead.add(name) \n\n    def getInheritanceOrder(self) -> List[str]:\n        def helper(r):\n            if r.val not in self.dead: ans.append(r.val)\n            for child in r.childs:\n                helper(child)                            \n        ans = []\n        helper(self.root)\n        return ans\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.pc = defaultdict(list)\n        self.deathset = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.pc[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.deathset.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        ans = []\n        self.recur(self.king, ans)\n        return ans\n        \n    def recur(self, name:str, ans:List[str]) -> None :\n        if name not in self.deathset:\n            ans.append(name)\n        for child in self.pc[name] :\n            self.recur (child, ans)\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.inh = {kingName: (None, True, [])}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.inh[parentName][-1].append(childName)\n        self.inh[childName] = (parentName, True, [])\n\n    def death(self, name: str) -> None:\n        p, _, ch = self.inh[name]\n        self.inh[name] = (p, False, ch)\n\n    def getInheritanceOrder(self) -> List[str]:\n        # print(self.inh)\n        order = [self.king]\n        s = set(order)\n        # inord = {k: cc[::-1] for k, (pp, _, cc) in self.inh.items()}\n        def fs(x):\n            p, a, ch = self.inh[x]\n            # if not inord[x]: #  no children or all of x's children are in curOrder:\n            #     if x != self.king:\n            #         fs(p)\n            # else:\n            for c in ch:\n                order.append(c)\n                s.add(c)\n                # inord[x].pop()\n                fs(c)\n        fs(self.king)\n        return [o for o in order if self.inh[o][1]]\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "\n#ThroneInheritance(string kingName) Initializes an object of the ThroneInheritance class. The name of the king is given as part of the constructor.\n#void birth(string parentName, string childName) Indicates that parentName gave birth to childName.\n#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.\n#string[] getInheritanceOrder() Returns a list representing the current order of inheritance excluding dead people.\nfrom collections import OrderedDict\nclass Person:\n    def __init__(self, name):\n        self.name = name\n        self.alive = True\n        self.children = []\n        self.parent = None\n        self._successor = None\n    \n    @property\n    def successor():\n        if not self.children:\n            return self.parent\n        else:\n            return self.children[0]\n    \n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = Person(kingName)\n        self.people = {kingName: self.king}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.people[parentName]\n        child = Person(childName)\n        child.parent = parent\n        self.people[childName] = child\n        parent.children.append(child)\n\n    def death(self, name: str) -> None:\n        person = self.people[name]\n        person.alive = False     \n        \n    def successor(self, x, curOrder):\n        curNames = set(curOrder)\n        if not x.children or set([c.name for c in x.children]) <= curNames:\n            if x.name == self.king.name:\n                return None\n            else:\n                return self.successor(x.parent, curOrder)\n        else:\n            for c in x.children:\n                if c.name not in curNames:\n                    return c.name\n                \n    def inorder(self, t):\n        res = [t.name]\n        for c in t.children:\n            res += self.inorder(c)\n        return res\n\n    def getInheritanceOrder(self) -> List[str]:\n        return [name for name in self.inorder(self.king) if self.people[name].alive]\n        \n        \n    def a():\n        curOrder = [self.king.name]\n        x = self.king\n        while len(curOrder) < len(self.people):\n            newsuc = self.successor(x, curOrder)\n            x = self.people[newsuc]\n            curOrder.append(newsuc)\n        return [name for name in curOrder if self.people[name].alive]\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self):\n        self.name = None\n        self.children = []\n        self.parent = None\n        self.isDead = False\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node()\n        self.root.name = kingName\n        self.lookup = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        curr = Node()\n        curr.name = childName\n        curr.parent = parentName\n        \n        self.lookup[parentName].children.append(curr)\n        self.lookup[childName] = curr\n\n    def death(self, name: str) -> None:\n        self.lookup[name].isDead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        return self.dfs(self.root)\n        \n    def dfs(self, node):\n        if node.isDead:\n            result = []\n        else:\n            result = [node.name]\n        for c in node.children:\n            result += self.dfs(c)\n                \n        return result\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = kingName\n        self.deathed = set()\n        self.hmap = {kingName: []}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.hmap[parentName].append(childName)\n        self.hmap[childName] = []\n        \n\n    def death(self, name: str) -> None:\n        self.deathed.add(name)\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        \n        def dfs(node):\n            # nonlocal ans\n            for st in self.hmap[node]:\n                if st not in self.deathed:\n                    ans.append(st)\n                dfs(st)\n        ans = [self.root] if self.root not in self.deathed else []\n        dfs(self.root)\n        return ans\n            \n            \n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Member:\n    \n    def __init__(self, name):\n        self.name = name\n        self.alive = True\n        self.nextChild = None\n        self.nextSibling = None\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.members = {}\n        self.lastChild = {}\n        \n        self.king = Member(kingName)\n        self.members[kingName] = self.king\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.members[parentName]\n        \n        child = Member(childName)\n        self.members[childName] = child\n        \n        if parentName in self.lastChild:\n            member = self.lastChild[parentName]\n            member.nextSibling = child\n        else:\n            parent.nextChild = child\n        self.lastChild[parentName] = child\n        \n\n    def death(self, name: str) -> None:\n        self.members[name].alive = False\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        inheritanceOrder = []\n        \n        def traverseInOrder(member):\n            if member is None:\n                return\n            \n            if member.alive:\n                inheritanceOrder.append(member.name)\n            traverseInOrder(member.nextChild)\n            traverseInOrder(member.nextSibling)\n        \n        traverseInOrder(self.king)\n        return inheritanceOrder\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "from collections import defaultdict as dict\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.graph = dict(list)\n        self.visited = {}\n        self.death_set = set()\n        self.kingName = kingName\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        self.graph[parentName].append(childName)\n        \n        if parentName not in list(self.visited.keys()):\n            self.visited[parentName] = False\n        if childName not in list(self.visited.keys()):\n            self.visited[childName] = False\n        \n    def death(self, name: str) -> None:\n        self.death_set.add(name)\n        \n    def getInheritanceOrder(self) -> List[str]:\n        stack = []\n        u = self.kingName\n        self.get_dfs(u, self.visited, self.graph, stack)\n        self.reset_visit(self.visited)\n        return stack\n    \n    \n    def get_dfs(self, u, visited, graph, stack):\n        visited[u] = True\n        if u not in self.death_set:\n            stack.append(u)\n        \n        for v in graph[u]:\n            if visited[v]==False:\n                self.get_dfs(v, visited, graph, stack)\n                \n    def reset_visit(self, visited):\n        for key in list(visited.keys()):\n            visited[key]=False\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.alive = True\n        self.children = deque()\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.map = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        p = self.map[parentName]\n        q = Node(childName)\n        p.children.appendleft(q)\n        self.map[childName] = q\n\n    def death(self, name: str) -> None:\n        self.map[name].alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        ret = []\n        s = [self.root]\n        while s:\n            p = s.pop()\n            if p.alive:\n                ret.append(p.name)\n            s.extend(p.children)\n        return ret\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.lineageTree = [kingName, []]\n        self.lineageLocs = {kingName: self.lineageTree}\n        self.deaths = set([])\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        parentLoc = self.lineageLocs[parentName]\n        parentLoc[1].append([childName, []])\n        self.lineageLocs[childName] = parentLoc[1][-1]\n        \n    def death(self, name: str) -> None:\n        self.deaths.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        def doit(node, deaths):\n            if node == []:\n                return []\n            res = []\n            if node[0] not in deaths:\n                res.append(node[0])\n            for childNode in node[1]:\n                res = res + doit(childNode, deaths)\n            return res\n        return doit(self.lineageTree, self.deaths)\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class node:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.isdead = False\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = node(kingName)\n        self.m = {kingName : self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        p = self.m[parentName]\n        c = node(childName)\n        p.children.append(c)\n        self.m[childName] = c\n\n    def death(self, name: str) -> None:\n        self.m[name].isdead = True\n\n    def getInheritanceOrder(self) -> List[str]:\n        cur = self.root\n        res = []\n        def helper(cur):\n            if not cur.isdead:\n                res.append(cur.name)\n            for c in cur.children:\n                helper(c)\n                \n        helper(cur)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class TreeNode:\n    def __init__(self, personName):\n        self.name = personName;\n        self.children = [];\n        self.parent = None;\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = TreeNode(kingName);\n        self.dead = set();\n        self.treeMap = {};\n        self.treeMap[kingName] = self.king;\n        self.ret = [];\n    \n    \n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.treeMap[parentName];\n        child = TreeNode(childName);\n        \n        self.treeMap[childName] = child;\n        child.parent = parent;\n        \n        parent.children.append(child);\n\n    def death(self, name: str) -> None:\n        self.dead.add(name);\n\n    def getInheritanceOrder(self) -> List[str]:\n        self.ret = [];\n        def helper(node):\n            if node.name not in self.dead:\n                self.ret.append(node.name);\n            for i, child in enumerate(node.children):\n                helper(node.children[i]);\n            \n        helper(self.king);\n        return self.ret;\n        \n        \n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class node:\n    def __init__(self,name):\n        self.data=name\n        self.children=[]\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root=node(kingName)\n        self.dic={}\n        self.dic[kingName]=self.root\n        self.dead={}\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        curr=self.dic[parentName]\n        new=node(childName)\n        curr.children.append(new)\n        self.dic[childName]=new\n    def death(self, name: str) -> None:\n        self.dead[name]=True\n\n    def getInheritanceOrder(self) -> List[str]:\n        def dfs(node,ans):\n            if node.data not in self.dead:\n                ans.append(node.data)\n            for child in node.children:\n                dfs(child,ans)\n        ans=[]\n        dfs(self.root,ans)\n        return ans\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.name = name\n        self.children = []\n        self.parent = None\n        \n    def add(self, child_node):\n        self.children.append(child_node)\n        child_node.parent = self\n    \n    def die(self):\n        index = self.parent.children.index(self)\n        #print(index, self.parent.children)\n        self.parent.children[index:index] = self.children\n        self.parent.children.remove(self) # remove from parents children\n        for child in self.children:\n            child.parent = self.parent\n        self.parent = None\n\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.nodes = {}\n        root = Node(\\\"\\\")\n        self.nodes[\\\"\\\"] = root\n        self.birth(\\\"\\\", kingName)\n        \n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.nodes[childName] = child\n        parent = self.nodes[parentName]\n        parent.add(child)\n\n    def death(self, name: str) -> None:\n        self.nodes[name].die()\n        del self.nodes[name]\n\n    def getInheritanceOrder(self) -> List[str]:\n        path = []\n        def dfs(node):\n            path.append(node.name)\n            for child in node.children:\n                dfs(child)\n        dfs(self.nodes[\\\"\\\"])\n        return path[1:]\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class Node:\n    def __init__(self, val):\n        self.val = val\n        self.child = []   # list of Nodes\n        self.alive = True\n        \nclass ThroneInheritance:\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.dic = {kingName: self.root}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        self.dic[parentName].child.append(child)\n        self.dic[childName] = child\n\n    def death(self, name: str) -> None:\n        self.dic[name].alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        # dfs\n        res = []\n        def dfs(node):\n            if not node: return\n            if node.alive: res.append(node.val)\n            for n in node.child:\n                dfs(n)\n        dfs(self.root)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.g = defaultdict(list)\n        self.king_name = kingName\n        self.g[kingName] = list()\n        self.parent = {}\n        self.d = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.g[parentName].append(childName)\n        self.parent[childName] = parentName\n\n    def death(self, name: str) -> None:\n        self.d.add(name)\n        return None\n\n    def getInheritanceOrder(self) -> List[str]:\n        def successor(node, order, order_set):\n            if not self.g[node] or set(self.g[node]) & order_set == set(self.g[node]):\n                if node == self.king_name:\n                    return\n                else:\n                    successor(self.parent[node], order, order_set)\n            else:\n                for n in self.g[node]:\n                    if n not in order_set:\n                        order.append(n)\n                        order_set.add(n)\n                        return\n        order = [self.king_name]\n        order_set = set(order)\n        added = True\n        while added:\n            prev_size = len(order)\n            successor(order[-1], order, order_set)\n            added = prev_size < len(order)\n        return [o for o in order if o not in self.d]\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Member:\n    def __init__(self,name):\n        self.name = name\n        self.children = list()\n        self.isAlive = True\n        \nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.kingdom = dict()\n        self.king = Member(kingName)\n        self.kingdom[kingName] = self.king\n\n    def birth(self, parentName: str, childName: str) -> None:\n        parent = self.kingdom[parentName]\n        child  = Member(childName)\n        self.kingdom[childName] = child\n        parent.children.append(child)\n\n    def death(self, name: str) -> None:\n        member = self.kingdom[name]\n        member.isAlive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        stack = [self.kingdom[self.king.name],]\n        while stack:\n            member = stack.pop()\n            if member.isAlive: order.append(member.name)\n            for i in range(len(member.children)-1,-1,-1):\n                stack.append(member.children[i])\n                \n        return order\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class TreeNode:\n    \n    def __init__(self, val):\n        self.val = val\n        self.children = []\n        self.siblings = []\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        \n        self.root = TreeNode(kingName)\n        self.mapping = collections.defaultdict()\n        self.mapping[kingName] = self.root\n        self.order = [kingName]\n        self.parent = collections.defaultdict()\n        self.dead = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        \n        self.mapping[parentName].children.append(childName)\n        self.mapping[childName] = TreeNode(childName)\n        self.parent[childName] = parentName\n        \n    def death(self, name: str) -> None:\n        \n        self.dead.add(name)\n        \\\"\\\"\\\"if name == 'king' or self.root.val == name:\n            siblings = self.root.children[1:]\n            print(name, 'name')\n            self.root = self.mapping[self.root.children[0]]\n            # move all sibilings to new root's children\n            self.root.siblings += siblings\n        else:\n            parent_node = self.parent[name]\n            idx = self.mapping[parent_node].children.index(name)\n            # move death's parent to its grandparent\n            for child in reversed(self.mapping[name].children):\n                self.parent[child] = parent_node\n                self.mapping[parent_node].children.insert(idx, child)\n            self.mapping[self.parent[name]].children.remove(name)\\\"\\\"\\\"\n        \n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        def dfs(node):\n            res.append(node.val)\n            for child in node.children:\n                dfs(self.mapping[child])\n        dfs(self.root)\n        return [name for name in res if name not in self.dead]\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "import collections\n\nclass Node: \n    def __init__(self, name): \n        self.name = name\n        self.alive=True\n        self.children=[]\n    \n    def addChild(self, node): \n        self.children.append(node)\n        \n    def setDeath(self): \n        self.alive=False\n       \n    def getName(self): \n        return self.name\n    \n    def getChildren(self): \n        return self.children\n    \n    def isAlive(self): \n        return self.alive\n\nclass ThroneInheritance:\n    \n    def __init__(self, kingName: str):\n        self.kingName=kingName\n        self.name_node = {kingName: Node(kingName)}\n\n    def birth(self, parentName: str, childName: str) -> None:\n        child = Node(childName)\n        parent = self.name_node[parentName]\n        parent.addChild(child)\n        self.name_node[childName]=child\n\n    def death(self, name: str) -> None:\n        person=self.name_node[name]\n        person.setDeath()\n        \n    def getInheritanceOrder(self) -> List[str]:\n        # apply DFS\n        \n        def dfs(node): \n            if node: \n                name = node.getName()\n                if node.isAlive():\n                    order.append(name)\n                children = node.getChildren()\n                for child in children: \n                    dfs(child)\n        node=self.name_node[self.kingName]\n        order=[]\n        dfs(node)\n        return order\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Person:\n    def __init__(self, name):\n        self.name = name\n        self.alive = True\n        self.children = []\n\n    def __str__(self):\n        parts = []\n        parts.append(self.name)\n        if self.alive == False:\n            parts.append(\\\"dead\\\")\n        parts.append(\\\"(\\\")\n        for child in self.children:\n            parts.append(child.name)\n        parts.append(\\\")\\\")\n        return \\\" \\\".join(parts)\n\nclass ThroneInheritance:\n\n    def createPerson(self, name):\n        p = Person(name)\n        self.lookup[name] = p\n        return p\n    \n    def __init__(self, kingName: str):\n        self.lookup = dict()\n        self.king = self.createPerson(kingName)\n        \n        print(self.lookup)\n        print(self.king)\n\n    def birth(self, parentName: str, childName: str) -> None:\n        p = self.lookup[parentName]\n        child = self.createPerson(childName)\n        p.children.append(child)\n        print(p)\n\n    def death(self, name: str) -> None:\n        self.lookup[name].alive = False\n\n    def getInheritanceOrder(self) -> List[str]:\n        order = []\n        def doit(p):\n            if p != None:\n                if p.alive:\n                    order.append(p.name)\n                for c in p.children:\n                    doit(c)\n        doit(self.king)\n        return order\n        \n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()", "class ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.king = kingName\n        self.family = defaultdict(list)\n        self.deadName = set()\n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.family[parentName].append(childName)\n\n    def death(self, name: str) -> None:\n        self.deadName.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        res = []\n        def dfs(name):\n            if name not in self.deadName:\n                res.append(name)\n            for n in self.family[name]:\n                dfs(n)\n        dfs(self.king)\n        return res\n\n\n# Your ThroneInheritance object will be instantiated and called as such:\n# obj = ThroneInheritance(kingName)\n# obj.birth(parentName,childName)\n# obj.death(name)\n# param_3 = obj.getInheritanceOrder()\n", "class Node:\n    def __init__(self, name):\n        self.children = []\n        self.name = name\n        \n    def add_children(self, name):\n        node = Node(name)\n        self.children.append(node)\n        return node\n\nclass ThroneInheritance:\n\n    def __init__(self, kingName: str):\n        self.root = Node(kingName)\n        self.dead = set()\n        self.lookup = dict()\n        self.lookup[kingName] = self.root\n        \n\n    def birth(self, parentName: str, childName: str) -> None:\n        self.lookup[childName] = self.lookup[parentName].add_children(childName)\n\n    def death(self, name: str) -> None:\n        self.dead.add(name)\n\n    def getInheritanceOrder(self) -> List[str]:\n        results = []\n        \n        def dfs(x):\n            nonlocal results\n            \n            if x.name not in self.dead:\n                results.append(x.name)\n            for y in x.children:\n                dfs(y)\n            \n        dfs(self.root)\n        return results\n    \n"]