Connecting Islands

We want to connect a group of islands with bridges so that any island can be reached from any other island. Because the cost of a bridge is proportional to its length, we want to keep the total cost down by minimizing the total length of the bridges needed to connect all the islands. Write a program that determines this minimum total bridge length.

Each island is represented by a polygon, and to keep things simple a bridge may only run between corners (vertices) of two different polygons. A bridge may only run over water; it may not pass over any island's land. Two bridges are, however, allowed to cross each other. Note that the shape of an island may be non-convex.

The first line contains the number of test cases.

Each test case begins with a line containing the number of islands $N$ ($2 \le N \le 15$). The next $N$ lines each describe one island. An island is a polygon given by an integer $P$ ($1 \le P \le 25$), the number of vertices, followed by $P$ coordinate pairs $x\ y$. Each coordinate is an integer in the range $[-1000, 1000]$. The vertices are listed in order, so that connecting consecutive vertices, and the last vertex back to the first, traces the island's shore.

It is guaranteed that islands neither touch nor intersect.

For each test case, print two lines in the following format:

The minimal interconnect consists of B bridges
with a total length of L.

Here $B$ is the number of bridges built and $L$ is their total length, printed with exactly three digits after the decimal point.