Day 07: Handy Haversacks

After the grueling peer-evaluation marathon, you head down to the Bocal's Lost & Found to retrieve your prized possession: your legendary shiny gold bag.

However, the Bocal enforces a ludicrously strict locker storage policy across the cluster: every colored bag must be nested inside other bags according to specific regulations.

You are handed the official list of containment rules detailing which bags may contain others.

Part 1

You want to know your options for carrying or disguising your bag. How many bag colors can, directly or indirectly, contain at least one shiny gold bag ?

Example

Consider these locker rules:

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.

In this example:

• A bright white bag can directly contain a shiny gold bag.
• A muted yellow bag can directly contain two shiny gold bags.
• A dark orange bag contains bright white and muted yellow bags, both of which can contain a shiny gold bag.
• A light red bag also contains bright white and muted yellow bags.
• Other bag colors cannot eventually contain a shiny gold bag.

In total, there are 4 different bag colors that can eventually contain at least one shiny gold bag.

Analyze the official Bocal rulebook from your input file. How many bag colors can eventually contain at least one shiny gold bag?