지도 색칠하기 익스트림

다른 세계로 넘어온 당신은 그 세계의 지도를 한 장 얻었다. 이 세계에는 여러 나라가 있다. 각 나라의 영토는 하나로 이어져 있고, 지도에는 국경선으로 둘러싸인 2차원 평면 위의 단순 다각형으로 그려져 있다.

이 세계가 낯선 당신은 나라를 구분하려고 지도에 색을 칠하려 한다. 인접한 두 나라를 같은 색으로 칠하면 구분하기 어려우니, 인접한 나라는 서로 다른 색으로 칠하려 한다. 여기서 두 나라의 국경선에 길이가 0보다 큰 공통 선분이 하나라도 있으면 두 나라가 인접하다고 정의한다. 국경선이 점에서만 닿는 두 나라는 인접하지 않다.

이 세계의 화폐가 없어서 색을 많이 준비하기는 어렵다. 인접한 나라를 서로 다른 색으로 칠하려면 색이 최소 몇 개 필요한가?

입력은 여러 개의 데이터 세트로 이루어진다. 데이터 세트의 개수는 35개 이하이다.

각 데이터 세트의 형식은 다음과 같다.

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

각 데이터 세트의 첫 줄에는 이 세계의 나라 수를 나타내는 정수 $n$ ($1 \le n \le 35$)이 주어진다.

그다음에는 $n$개 나라를 나타내는 다각형 정보가 이어진다. $i$번째 다각형 정보의 첫 줄에는 꼭짓점 수를 나타내는 정수 $m_i$ ($3 \le m_i \le 50$)가 주어진다. 이어지는 $m_i$개 줄에는 꼭짓점의 좌표가 반시계 방향 순서로 주어진다. 그중 $j$번째 줄에는 $i$번째 다각형의 $j$번째 꼭짓점 좌표를 나타내는 두 정수 $x_{i,j}$와 $y_{i,j}$ ($|x_{i,j}|, |y_{i,j}| \le 10^3$)가 주어진다.

다음은 가정해도 된다.

• 각 다각형의 넓이는 0보다 크다.
• 같은 다각형의 두 꼭짓점은 좌표가 서로 다르다.
• 같은 다각형의 두 선분은 각 꼭짓점에서 정확히 두 선분이 만나는 경우를 빼면 공통점이 없다.
• 두 다각형이 겹치는 넓이는 없다.

입력의 끝은 0 하나만 있는 줄로 표시한다.

각 데이터 세트마다 인접한 나라를 서로 다른 색으로 칠할 때 필요한 색의 최소 개수를 한 줄에 출력한다.