class ThroneInheritance {
 public:
  ThroneInheritance(string kingName) : kingName(kingName) {}

  void birth(string parentName, string childName) {
    family[parentName].push_back(childName);
  }

  void death(string name) {
    dead.insert(name);
  }

  vector<string> getInheritanceOrder() {
    vector<string> ans;
    dfs(kingName, ans);
    return ans;
  }

 private:
  unordered_set<string> dead;
  unordered_map<string, vector<string>> family;
  string kingName;

  void dfs(const string& name, vector<string>& ans) {
    if (!dead.count(name))
      ans.push_back(name);
    if (!family.count(name))
      return;

    for (const string& child : family[name])
      dfs(child, ans);
  }
};

class ThroneInheritance {
  public ThroneInheritance(String kingName) {
    this.kingName = kingName;
  }

  public void birth(String parentName, String childName) {
    family.putIfAbsent(parentName, new ArrayList<>());
    family.get(parentName).add(childName);
  }

  public void death(String name) {
    dead.add(name);
  }

  public List<String> getInheritanceOrder() {
    List<String> ans = new ArrayList<>();
    dfs(kingName, ans);
    return ans;
  }

  private Set<String> dead = new HashSet<>();
  private Map<String, List<String>> family = new HashMap<>();
  private String kingName;

  private void dfs(final String name, List<String> ans) {
    if (!dead.contains(name))
      ans.add(name);
    if (!family.containsKey(name))
      return;

    for (final String child : family.get(name))
      dfs(child, ans);
  }
}