Crowded Forest Wildlife

The WWF volunteers are back again to collect more wildlife from Gump Forest! Animals have moved around the forest, and some trails are getting more crowded!. Lisa finds that the same type of animal may now be found living on multiple trails connected to the same clearing.
Elsewhere in the forest trails may have no animals living on it. If a trail has no animals, the WWF truck can drive along it any time without collecting any animals. Can Lisa still guide the WWF volunteers through the forest and fill up their truck?

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. There are no more than 1000 trails and the number of animals on each trail will not exceed 30. 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 either ”Succeeded” if there is a path through the Gump Forest that can fill up the truck and return it to the entrance. Otherwise
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.)

1 3 puma
2 3 lynx
0 3 toad
0 1
0 2
puma lynx
lynx toad
puma lynx toad
1 0 puma
1 2 puma
2 0 puma
puma puma puma 
puma

Succeeded
Succeeded
Failed
Succeeded
Failed

HDU 2010-05 Programming Contest