Wormholes

Humanity's time on Earth is running out. Cooper and Amelia have volunteered for a mission beyond this galaxy to find out whether mankind has a future among the stars. Astronomers have identified several potentially habitable planets and found that some pairs of them are joined by wormholes. Travelling through a wormhole covers a distance of 0. Between any other two planets the travel distance is the Euclidean distance.

Given the planets and the wormholes, find the shortest travel distance between the two planets of each query.

• The first line holds one integer $T$ ($1 \le T \le 10$), the number of test cases.
• Each test case consists of a planet list, a wormhole list, and a query list.
• The planet list starts with one integer $p$ ($1 \le p \le 60$), the number of planets. Then follow $p$ lines, each holding a planet name and its integer coordinates as name x y z ($0 \le x, y, z \le 2 \times 10^6$). A name consists only of ASCII letters and digits, always starts with a letter, and is at most 50 characters long. Names are case-sensitive, so Earth and earth are distinct planets. Coordinates are given in parsecs.
• The wormhole list starts with one integer $w$ ($0 \le w \le 40$), the number of wormholes. Then follow $w$ lines, each holding two planet names separated by a space. The first name is the entrance and the second name is the exit. A wormhole can be traversed only from its entrance to its exit, and you cannot enter it at its exit. Both names appear in the planet list above.
• The query list starts with one integer $q$ ($1 \le q \le 20$), the number of queries. Then follow $q$ lines, each holding two planet names separated by a space. Both names appear in the planet list, and the same name may appear twice.

For each test case, first print Case i: on its own line, where $i$ is the number of the test case, counting from 1.

Then, for each query of that test case, print one line reading The distance from planet1 to planet2 is d parsecs., where planet1 and planet2 are the names as given in the query and d is the shortest travel distance from planet1 to planet2, rounded to the nearest integer. If the value falls exactly halfway between two integers, round up.