def trace_up(all_bags, bag):
    """
    For the input bag "bag", trace the path upwards along all of its parents,
    which are the bags that can  hold it.
    """
    parents = []
    if len(bag.held_by) == 0:
        return parents

    for bag_type in bag.held_by:
        parents.append(bag_type)
        held_bag = all_bags[bag_type]
        for parent in trace_up(all_bags, held_bag):
            parents.append(parent)
    return list(set(parents))