Color the Map Extreme

You have just moved to another world and been handed a map of it. The world has several countries. Each country's territory is connected, and the map draws it as a simple polygon in the plane bounded by that country's border segments.

The world is new to you, so you want to paint the countries on the map to tell them apart. Painting two adjacent countries with the same color makes them hard to tell apart, so you want adjacent countries to get different colors. Two countries are adjacent when their borders share at least one segment whose length is strictly greater than 0. Two countries whose borders touch only at points are not adjacent.

You do not have this world's currency, so preparing many colors is hard. What is the smallest number of colors that paints the map so that adjacent countries get different colors?

The input holds several datasets. There are at most 35 datasets.

Each dataset has this format.

n
m1
x1,1 y1,1
:
:
x1,m1 y1,m1
:
:
mn
xn,1 yn,1
:
:
xn,mn yn,mn

The first line of a dataset holds an integer $n$ ($1 \le n \le 35$), the number of countries in the world.

The rest of the dataset describes the $n$ polygons that represent the countries. The first line of the $i$-th polygon holds an integer $m_i$ ($3 \le m_i \le 50$), the number of vertices. The next $m_i$ lines give the coordinates of the vertices in counter-clockwise order. The $j$-th of them holds two integers $x_{i,j}$ and $y_{i,j}$ ($|x_{i,j}|, |y_{i,j}| \le 10^3$), the coordinates of the $j$-th vertex of the $i$-th polygon.

You may assume the following.

• Every polygon has an area greater than 0.
• Two vertices of the same polygon have distinct coordinates.
• Two segments of the same polygon have no common point, except that exactly two segments meet at each vertex.
• Two polygons share no area.

A line holding a single zero ends the input.

For each dataset, print on one line the smallest number of colors that paints the map so that adjacent countries get different colors.