섬 연결하기

여러 개의 섬을 다리로 연결하여, 어떤 섬에서든 다른 모든 섬으로 갈 수 있도록 만들려고 합니다. 다리를 놓는 비용은 다리의 길이에 비례하므로, 전체 비용을 줄이려면 모든 섬을 연결하는 데 필요한 다리들의 총 길이를 최소로 해야 합니다. 모든 섬을 서로 연결하는 데 필요한 다리들의 최소 총 길이를 구하는 프로그램을 작성하세요.

각 섬은 다각형으로 주어지며, 다리는 서로 다른 두 다각형의 꼭짓점(코너) 사이에만 놓을 수 있습니다. 다리는 반드시 물 위로만 지나가야 하며, 어떤 섬의 육지 위로도 지날 수 없습니다. 단, 두 다리가 서로 교차하는 것은 허용됩니다. 섬의 모양은 볼록하지 않을 수도 있습니다.

첫 번째 줄에 테스트 케이스의 개수가 주어집니다.

각 테스트 케이스의 첫 줄에는 섬의 개수 $N$ ($2 \le N \le 15$)이 주어집니다. 이어지는 $N$개의 줄에는 각각 하나의 섬이 주어집니다. 한 섬은 꼭짓점의 개수 $P$ ($1 \le P \le 25$)와, 그 뒤에 이어지는 $P$개의 좌표쌍 $x\ y$로 이루어진 다각형입니다. 각 좌표는 $[-1000, 1000]$ 범위의 정수입니다. 꼭짓점들은 순서대로 주어지며, 연속한 꼭짓점들을 잇고 마지막 꼭짓점을 다시 첫 꼭짓점과 이으면 섬의 해안선이 됩니다.

섬들은 서로 닿거나 겹치지 않음이 보장됩니다.

각 테스트 케이스마다 다음 형식으로 두 줄을 출력합니다.

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

여기서 $B$는 놓은 다리의 개수, $L$은 다리들의 총 길이이며, $L$은 소수점 아래 정확히 세 자리까지 출력합니다.