Walking on Thin Ice

You are trying to cross a frozen river. Unfortunately the ice is not of uniform thickness: in some places it is thick enough to be safe to cross, while in others it is not. Before crossing, you sent out a lightweight robot to map where it is and is not safe to cross. Now you want to determine the minimum distance you must travel over unsafe ice to reach the other side of the river.

Model the river in the 2-D plane as the region between two infinitely long parallel lines. The edge of the river on your starting side is the line $y = 0$, and the opposite edge is the line $y = W$, where $W$ is the width of the river. The parts of the river that are safe to cross are given as simple polygons (each polygon does not intersect itself and has positive area). Every point of the river that does not lie in a safe area is unsafe to cross.

You may start crossing at any point on your side ($y = 0$) and may finish at any point on the far side ($y = W$).

The first line contains the number of data sets $K$, followed by the $K$ data sets, each of the following form.

The first line of a data set contains the width of the river $W$ and the number of safe areas $N$ ($1 \le W \le 1{,}000{,}000$, $1 \le N \le 100$). This is followed by $N$ lines. Line $i$ describes the $i$-th safe area and begins with the number of vertices $V$ ($3 \le V \le 20$). This is followed on the same line by $V$ pairs of integers giving the $x$ and $y$ coordinates of the vertices of the safe area in clockwise order.

Every $x$ coordinate is between $-1{,}000{,}000$ and $1{,}000{,}000$, and every $y$ coordinate is between $0$ and $W$. Every safe area is non-self-intersecting and has positive area, and no two safe areas intersect or touch.

For each data set, first output Data Set x: on a line by itself, where $x$ is its number (starting from 1). On the next line, output the minimum distance you must travel over unsafe ice to cross the river, rounded to two decimal places.

Output a single blank line between consecutive data sets (do not print a blank line after the last data set).