Color the Map

Time limit1sMemory limit128 MB

Summary

Given polygons grouped into named countries, determine the minimum colors needed so adjacent countries (sharing a border segment of positive length) differ, using geometric segment overlap detection to build the adjacency graph then graph coloring.

Level: Medium6 of 10
Topics: Geometry, Graph, Brute force
Solved: No attempts yet

Problem

You have obtained a map of a mysterious world you are about to explore. The map shows the whole region, divided into several countries whose borders are intricate. Because it is drawn in a single ink color, it is hard to tell at a glance which region belongs to which country, so you decide to color the map before setting out.

Each country consists of one or more territories, each of which is a simple polygon. The territories of one country need not touch one another, so a country may have disconnected territories. All territories of the same country must be given the same color. Two different countries may share a color, but two adjacent countries must be given different colors. Two countries are adjacent when any of their territories share a border of non-zero length; territories that meet only at a single point do not count as sharing a border.

Write a program that determines the least number of colors needed to color the map under these rules.

Input

The input consists of several maps. Each map begins with a line containing the total number of territories $n$ , a positive integer with $n \le 100$ . The data for the $n$ territories follow.

A territory with $m$ vertices is given in the following format:

String
x1 y1
x2 y2
...
xm ym
-1

String is the name of the country the territory belongs to: a sequence of alphanumeric characters, at least 1 and at most 20 characters long. When a country has several territories, the same name appears in each of them.

The remaining lines list the vertices of the territory. Each vertex line contains two nonnegative integers, the $x$ - and $y$ -coordinates, separated by a single space; neither coordinate exceeds 1000. The edges of the territory are obtained by connecting consecutive vertices, and by connecting the last vertex back to the first. A line containing only -1 marks the end of the vertex list. The number of vertices satisfies $m \le 100$ .

You may assume that every polygon is simple (its boundary neither crosses nor touches itself) and that no two polygons share a region of non-zero area. Each map contains at most 10 countries.

The end of the input is a line containing a single zero.

Output

For each map, output one line containing the least number of colors needed to color it under the stated rules.

Examples3

Example 1

Input

6
Blizid
0 0
60 0
60 60
0 60
0 50
50 50
50 10
0 10
-1
Blizid
0 10
10 10
10 50
0 50
-1
Windom
10 10
50 10
40 20
20 20
20 40
10 50
-1
Accent
50 10
50 50
35 50
35 25
-1
Pilot
35 25
35 50
10 50
-1
Blizid
20 20
40 20
20 40
-1
4
A1234567890123456789
0 0
0 100
100 100
100 0
-1
B1234567890123456789
100 100
100 200
200 200
200 100
-1
C1234567890123456789
0 100
100 100
100 200
0 200
-1
D123456789012345678
100 0
100 100
200 100
200 0
-1
0

Expected output

4
2

Example 2
Input
```
1
Alpha
0 0
10 0
10 10
0 10
-1
0
```
Expected output
```
1
```

Example 3

Input

Expected output