问题描述

你刚刚转移到了另一个世界，并获得了该世界的地图。这个世界中有几个国家。每个国家都有一个连通的领土，在地图上以简单多边形的形式绘制出来，它由平面上的边界线段组成。

你对这个世界不熟悉，所以你想在地图上绘制国家以区分它们。如果你用相同的颜色绘制相邻的国家，将很难区分这些国家。因此，你希望用不同的颜色绘制相邻的国家。这里，我们定义两个国家是相邻的，如果它们的边界有至少一条公共线段，其长度严格大于0。请注意，如果边界只在某些点接触并不算是相邻的国家。

因为你没有这个世界的货币，所以很难为你准备很多颜色。为了使相邻的国家可以用不同的颜色涂绘，最少需要几种颜色？

输入

输入由多个数据集组成。数据集的数量不超过35个。

每个数据集的格式如下：

$n$
$m\_1$
$x\_{1,1}$ $y\_{1,1}$
:
:
$x\_{1,m\_1}$ $y\_{1,m\_1}$
:
:
$m\_n$
$x\_{n,1}$ $y\_{n,1}$
:
:
$x\_{n,m\_n}$ $y\_{n,m\_n}$

每个数据集的第一行包含一个整数$n$（$1 \le n \le 35$），表示该世界中的国家数量。

每个数据集的其余部分描述了$n$个多边形表示的国家的信息。第$i$个多边形的信息的第一行包含一个整数$m\_i$（$3 \le m\_i \le 50$），表示多边形的顶点数量。接下来的$m\_i$行描述了以逆时针顺序排列的顶点的坐标。其中的第$j$行包含两个整数$x\_{i,j}$和$y\_{i,j}$（$|x\_{i,j}|, |y\_{i,j}| \le 10^3$），表示第$i$个多边形的第$j$个顶点的坐标。

你可以假设以下情况成立：

• 每个多边形的面积大于0。
• 同一个多边形的两个顶点具有不同的坐标。
• 相同多边形的两个线段除了在每个顶点处相交外没有其他共同点。
• 两个多边形没有共同的区域。

输入的结束由一行包含单个零表示。

输出

对于每个数据集，输出以一行形式绘制地图所需的最小颜色数量，使相邻的国家可以用不同的颜色绘制。

样例输入

1
3
0 0
1 0
0 1
4
4
0 0
10 0
10 10
0 10
4
10 0
20 0
20 10
10 10
4
0 10
10 10
10 20
0 20
4
10 10
20 10
20 20
10 20
3
4
-10 -10
2 2
10 10
-11 7
3
-1 -1
1 -1
0 0
3
0 0
3 -3
20 20
7
4
46 12
52 12
53 15
45 15
32
67 1
70 0
73 1
77 3
79 5
80 8
77 8
76 5
74 4
71 3
70 3
67 4
65 6
63 8
62 14
64 19
66 21
70 22
75 21
78 16
80 16
80 17
79 20
78 22
74 24
67 24
63 22
61 19
60 15
60 10
62 5
64 3
5
74 14
80 14
80 16
78 16
74 16
19
34 0
37 0
37 19
36 22
35 23
32 24
30 24
27 24
25 23
23 20
23 18
23 15
26 15
26 18
27 20
29 21
32 21
34 20
34 18
4
47 0
50 0
42 24
39 24
4
79 20
80 17
80 22
78 22
4
50 0
58 24
56 24
49 3
4
10
34 21
34 14
35 14
35 19
40 19
40 20
35 20
35 22
30 22
30 21
16
20 24
21 24
21 33
42 33
42 20
40 20
40 19
45 19
45 5
40 5
40 4
46 4
46 20
43 20
43 34
20 34
10
26 21
26 14
27 14
27 21
30 21
30 22
21 22
21 24
20 24
20 21
12
34 8
34 4
40 4
40 5
35 5
35 14
34 14
34 9
27 9
27 14
26 14
26 8
0```

### 样例输出

```plain
1
2
3
3
4```

### 来源

JAG Practice Contest for ACM-ICPC Asia Regional 2014