Sorted Trail Map

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.
The WWF are hoping to collect some endangered animals from Gump Forest. But their trail map is too confusing, since clearings and animals are listed in no particular order. Lisa decides to help the WWF volunteers by making up a sorted trail map of Gump Forest.

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 is the unsorted 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.
Every test case ends with "-1 -1".

The program output is a sorted trail map, where clearing numbers go up from 0, and animal names go from a to z. Trails are sorted by the number of the clearings at either end of the trail. All animals living on the trail are sorted in alphabetical order.

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

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

HDU 2010-05 Programming Contest