import itertools

def find_last_marked_nodes_brute_force(tree):
    nodes = list(tree.keys())
    all_permutations = list(itertools.permutations(nodes))
    last_marked_nodes_for_all_orders = []

    for marking_order in all_permutations:
        last_marked_nodes_for_current_order = simulate_marking(tree, marking_order)
        last_marked_nodes_for_all_orders.append(last_marked_nodes_for_current_order)

    final_result = determine_final_last_marked_nodes(last_marked_nodes_for_all_orders)
    return final_result

def simulate_marking(tree, marking_order):
    marked_nodes = set()
    last_marked_nodes = []

    for node_to_mark in marking_order:
        marked_nodes.add(node_to_mark)
        is_removable = False

        for neighbor in tree[node_to_mark]:
            if neighbor in marked_nodes:
                is_removable = True
                break

        if not is_removable:
            last_marked_nodes.append(node_to_mark)

    return last_marked_nodes

def determine_final_last_marked_nodes(all_last_marked_nodes):
    # Find the intersection of last marked nodes across all permutations
    if not all_last_marked_nodes:
        return []

    # Use the first list as the basis for intersection.
    intersection_of_last_marked_nodes = set(all_last_marked_nodes[0])

    # Iteratively find the intersection with other permutations' results.
    for last_marked_nodes in all_last_marked_nodes[1:]:
        intersection_of_last_marked_nodes.intersection_update(last_marked_nodes)

    return list(intersection_of_last_marked_nodes)

def example_usage():
    # Example tree structure represented as an adjacency list.
    example_tree = {
        'A': ['B', 'C'],
        'B': ['A', 'D'],
        'C': ['A', 'E'],
        'D': ['B'],
        'E': ['C']
    }
    
    result = find_last_marked_nodes_brute_force(example_tree)
    print(f"Last marked nodes: {result}")

if __name__ == "__main__":
    example_usage()

def find_last_marked_nodes(tree, marking_threshold):    last_marked_nodes = []
    # Helper function to determine if a node is a potential last marked node.
    def is_potential_last_marked(node):        if not node:
            return False
        
        if not node.children:
            return True
        
        # Check if the node satisfies criteria for being last marked.
        unmarked_children_count = 0
        for child in node.children:
            if not child.marked:
                unmarked_children_count += 1
        
        if unmarked_children_count <= (len(node.children) - marking_threshold):
            return True
            
        return False

    # Need to explore all nodes. 
    def explore_tree(node):
        if not node:
            return

        for child in node.children:
            explore_tree(child)

        # Add potential last marked nodes.
        if is_potential_last_marked(node):
            last_marked_nodes.append(node)

    explore_tree(tree)
    # Filter out nodes that depend on descendants' marking.
    final_last_marked_nodes = []
    for node in last_marked_nodes:
      is_truly_last = True
      for other_node in last_marked_nodes:
        if node != other_node and is_ancestor(node, other_node):
          is_truly_last = False
          break
      if is_truly_last:
        final_last_marked_nodes.append(node)

    return final_last_marked_nodes

def is_ancestor(node, potential_descendant):
  if not node or not potential_descendant:
    return False

  current = potential_descendant
  while current:
    if current == node:
      return True
    current = current.parent
  return False