Islands

The financial crisis in Greece has major consequences for the Greeks, especially for those who live on one of the many islands. Some of them cannot even afford to travel from one island to another by boat. They avoid going to another island as much as possible, but if they really must, they have to swim.

Since swimming is very exhausting and potentially dangerous, they would like to minimize the distance they have to swim. In that regard, swimming directly from island A to B may not be the best option. Instead, it might be better to swim from A to C, cross island C on foot, and then swim from C to B. The ideal travel plan could in fact involve many islands.

You are given a collection of islands, modeled as simple polygons. For two given islands, determine the smallest possible total distance one needs to swim in order to get from one island to the other. The total distance covered on land does not matter.

The first line contains one positive integer: the number of test cases, at most $100$. Then, for each test case:

• one line with one integer $n$ ($2 \le n \le 50$): the number of islands.
• one line with two space-separated integers $s$ and $d$ ($1 \le s, d \le n$, $s \ne d$): the start and destination islands of the intended journey, respectively.
• then, for each island:
  • one line with one integer $m$ ($3 \le m \le 50$): the number of vertices of the polygon describing the island.
  • $m$ lines, each with two space-separated integers $x_i$ and $y_i$ ($-10000 \le x_i, y_i \le 10000$): the coordinates of the $i$-th vertex.

The polygons (islands) are non-self-intersecting and do not overlap or touch each other. The vertices of each polygon are given in counterclockwise order.

For each test case:

• one line with one floating-point number: the minimum distance one needs to swim to get from the start island to the destination island, rounded to three decimal places.

The test data are such that an absolute error of at most $10^{-6}$ in the final answer does not change the result of the rounding.

The best route is not always a direct swim between the two islands. It can be shorter to swim to a nearby island, cross it on foot for free, and continue from there, so the optimal plan may pass through several intermediate islands. Only the segments crossed over water count toward the distance.