2014
02-10

# Collecting Forest Wildlife

Volunteers from the World Wildlife Foundation (WWF) have arrived in Springfield in a WWF truck.
They are collecting endangered animals living in the nearby Gump Forest, and are asking Lisa for help.
The WWF volunteers have given Lisa a map of the Gump Forest. The forest contains a number of clearings, and trails connecting the clearings. Different types of endangered animals live on each trail, no animals live in the clearings. Every trail must have at least one animal. Two trails connected to the same clearing cannot have the same animal.
Trails in the Gump Forest are narrow, so the WWF truck can only turn once it reaches the end of the trail and reaches a clearing. Exactly one endangered animal must be collected each time the truck drives along a trail. A trail may be traveled many times to pick up multiple animals.
TheWWF truck is filled with a number of cages, where each cage is designed for a single endangered species. Unfortunately, the truck is so filled with cages that the cages can only be filled in a certain order. Lisa has been asked to go with the WWF volunteers in their truck and guide the truck through
the Gump Forest and fill all the cages in the truck. The truck starts at the clearing at the entrance, goes through the forest, and returns to the entrance.

Animals are given as words(lowercases). Clearings are given as numbers. There may be up to 500 clearings.
Clearing 0 is always the entrance to Gump Forest.
The input begins with the Gump Forest trail map. Each line describes a trail between two clearings as a pair of numbers, followed by a list of animals living on the trail. Remaining lines begain with list of animals to be collected, in the order they are to be collected.

Animals are given as words(lowercases). Clearings are given as numbers. There may be up to 500 clearings.
Clearing 0 is always the entrance to Gump Forest.
The input begins with the Gump Forest trail map. Each line describes a trail between two clearings as a pair of numbers, followed by a list of animals living on the trail. Remaining lines begain with list of animals to be collected, in the order they are to be collected.

0 1 puma
1 2 frog
puma puma
puma frog frog puma
1 0 puma lynx
1 2 vole
toad puma lynx
0 1 0
Failed