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.

For each list of animals to be collected, your program should output the successful path through the Gump Forest as a sequence of numbers in the order clearings are visited, starting and ending with 0. If multiple successful paths are possible, print any successful path. If there is no successful path
through the Gump Forest that can fill up the truck and return it to the entrance, your program should output ”Failed” for that list.
Hint: Don’t try to solve the problem in a brute-force manner by enumerating all possible paths through Gump Forest. (It will take too long.)

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

0 1 0
0 1 2 1 0
0 2 1 0 1 0
Failed

HDU 2010-05 Programming Contest