Optical Fiber

A developing country wants to improve its communication infrastructure. Right now each city has its own local computer network, but there is no fast link between the cities. The country's communications ministry has decided to build a fast optical fiber network that connects every city.

To connect the cities, an optical fiber link is installed between selected pairs of cities. To keep the cost low, the links are chosen so that there is exactly one fiber path between any pair of cities. In other words, the $N$ cities and the $N-1$ links form a tree.

Each city installs a single optical router, and every fiber link that ends in that city is connected to this router. In each city there are several candidate locations where the router may be installed. Your task is to choose one installation location for every city so that the total length of optical fiber needed for the project is minimized.

The length of a link equals the Euclidean distance between the chosen locations of the two cities it connects.

The input consists of several test cases. The first line of each test case contains the number of cities $N$ ($1 \le N \le 1000$).

The description of each city follows. The first line for a city contains the city's (unique) name — capital letters only, at most 15 characters — and the number of candidate sites $C_i$ ($1 \le C_i \le 50$) where its router may be installed. Each of the next $C_i$ lines contains two integers $X$ and $Y$ ($-10000 \le X, Y \le 10000$), the coordinates of a candidate site.

After all cities have been described, $N-1$ lines follow, each containing the names of two cities that will be joined by a fiber link.

The end of the input is indicated by $N = 0$.

For each test case, print on a single line the minimum total length of optical fiber needed to connect all the cities. Round the answer to one decimal place.