살얼음 위를 걷다

얼어붙은 강을 건너려고 합니다. 그런데 얼음의 두께가 일정하지 않아서, 어떤 곳은 건너기에 충분히 두껍고 안전하지만 어떤 곳은 그렇지 않습니다. 강을 건너기 전에 가벼운 로봇을 보내 어디가 안전하고 어디가 위험한지 지도를 만들었습니다. 이제 강 반대편에 도달하기 위해 위험한 얼음 위를 지나야 하는 최소 거리를 구하려고 합니다.

강은 2차원 평면 위에서 서로 평행한 두 개의 무한히 긴 직선 사이의 영역으로 나타냅니다. 출발하는 쪽 강가는 직선 $y = 0$ 이고, 반대편 강가는 직선 $y = W$ 입니다. 여기서 $W$ 는 강의 폭입니다. 강에서 안전하게 건널 수 있는 영역은 단순 다각형으로 주어집니다(다각형은 자기 자신과 교차하지 않으며 넓이가 0보다 큽니다). 안전 영역에 속하지 않는 강 위의 모든 점은 위험합니다.

강을 건너기 시작하는 지점은 출발 쪽 강가($y = 0$)의 임의의 점이 될 수 있고, 건너기를 마치는 지점은 반대편 강가($y = W$)의 임의의 점이 될 수 있습니다.

첫 줄에는 데이터 집합의 개수 $K$ 가 주어지고, 이어서 $K$ 개의 데이터 집합이 다음 형식으로 주어집니다.

각 데이터 집합의 첫 줄에는 강의 폭 $W$ 와 안전 영역의 개수 $N$ 이 주어집니다($1 \le W \le 1{,}000{,}000$, $1 \le N \le 100$). 이어서 $N$ 개의 줄이 주어집니다. $i$ 번째 줄은 $i$ 번째 안전 영역을 나타내며, 먼저 그 안전 영역의 꼭짓점 개수 $V$ 가 주어집니다($3 \le V \le 20$). 그 뒤로 같은 줄에 $V$ 개의 정수 쌍이 주어지는데, 이는 안전 영역의 꼭짓점들의 $x$, $y$ 좌표를 시계 방향으로 나열한 것입니다.

모든 $x$ 좌표는 $-1{,}000{,}000$ 이상 $1{,}000{,}000$ 이하이고, 모든 $y$ 좌표는 $0$ 이상 $W$ 이하입니다. 모든 안전 영역은 자기 자신과 교차하지 않고 넓이가 양수이며, 서로 다른 두 안전 영역은 교차하거나 맞닿지 않습니다.

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력합니다. 여기서 $x$ 는 데이터 집합의 번호입니다(1부터 시작). 다음 줄에는 강을 건너기 위해 위험한 얼음 위를 지나야 하는 최소 거리를 소수점 아래 둘째 자리까지 반올림하여 출력합니다.

연속한 두 데이터 집합 사이에는 빈 줄을 하나 출력합니다(마지막 데이터 집합 뒤에는 빈 줄을 출력하지 않습니다).