섬

그리스의 금융 위기는 그리스인들, 특히 수많은 섬 중 하나에 사는 사람들에게 큰 영향을 미쳤다. 그들 가운데 일부는 배를 타고 섬에서 섬으로 이동할 형편조차 되지 못한다. 그래서 되도록 다른 섬으로 건너가는 일을 피하지만, 정말로 건너가야만 할 때에는 헤엄쳐서 이동해야 한다.

헤엄치기는 매우 힘들고 위험할 수 있으므로, 이들은 헤엄쳐야 하는 거리를 최대한 줄이고 싶어 한다. 이때 섬 A에서 섬 B로 곧장 헤엄치는 것이 항상 최선은 아니다. 예를 들어 A에서 C로 헤엄친 뒤 섬 C를 걸어서 가로지르고, 다시 C에서 B로 헤엄치는 편이 더 이로울 수 있다. 실제로 가장 좋은 이동 경로는 여러 섬을 거치게 될 수도 있다.

섬들은 단순 다각형으로 주어진다. 두 섬이 주어질 때, 한 섬에서 다른 섬으로 이동하기 위해 헤엄쳐야 하는 총 거리의 최솟값을 구하여라. 육지 위에서 이동한 거리는 전혀 중요하지 않다(비용에 포함되지 않는다).

첫째 줄에 테스트 케이스의 개수를 나타내는 양의 정수가 주어진다(최대 $100$). 그다음 각 테스트 케이스마다 다음이 주어진다.

• 한 줄에 정수 $n$ ($2 \le n \le 50$): 섬의 개수.
• 한 줄에 공백으로 구분된 두 정수 $s$와 $d$ ($1 \le s, d \le n$, $s \ne d$): 각각 이동의 출발 섬과 도착 섬.
• 이어서 각 섬마다:
  • 한 줄에 정수 $m$ ($3 \le m \le 50$): 그 섬을 나타내는 다각형의 꼭짓점 개수.
  • $m$개의 줄에 각각 공백으로 구분된 두 정수 $x_i$와 $y_i$ ($-10000 \le x_i, y_i \le 10000$): $i$번째 꼭짓점의 좌표.

다각형(섬)은 자기 자신과 교차하지 않으며, 서로 겹치거나 닿지도 않는다. 각 다각형의 꼭짓점은 반시계 방향으로 주어진다.

각 테스트 케이스마다:

• 한 줄에 실수 하나: 출발 섬에서 도착 섬까지 이동하기 위해 헤엄쳐야 하는 최소 거리를 소수점 아래 셋째 자리까지 반올림하여 출력한다.

테스트 데이터는 최종 답에 절대 오차 $10^{-6}$ 이하가 있어도 반올림 결과가 달라지지 않도록 주어진다.

최적 경로가 항상 두 섬 사이를 곧장 헤엄치는 것은 아니다. 가까운 섬으로 헤엄쳐 간 뒤 그 섬을 걸어서(비용 없이) 가로지르고 이어서 나아가는 편이 더 짧을 수 있으므로, 최적의 이동 계획은 여러 중간 섬을 거칠 수 있다. 거리에는 물 위를 지나는 구간만 포함된다.