Color the Map#3201

Color the Map

1 second

64 megabytes

Medium

You were lucky enough to get a map just before entering the legendary magical mystery world. The map shows the entire area of your planned exploration, including several countries with complicated borders. The map is clearly drawn, but only in sepia ink; it is difficult to quickly recognize which region belongs to which country, and this might bring you into severe danger. You decide to color the map before entering the area. "A good deal depends on preparation," you say to yourself.

Each country has one or more territories, each of which is a polygon. Territories belonging to the same country may or may not touch each other—that is, a country might have disconnected territories. All the territories belonging to the same country must be assigned the same color. You may assign the same color to more than one country, but to avoid confusion, any two countries that are "adjacent" must receive different colors. Two countries are considered "adjacent" if any of their territories share a border of non-zero length.

Write a program to determine the minimum number of colors needed to color the map.

Input

The input consists of several map descriptions. Each map starts with a line containing the total number of territories $n$ , followed by the description of each territory. $n$ is a positive integer not exceeding $100$ .

The data for a territory with $m$ vertices is specified as follows:

The first item: $String x_{1} y_{1} x_{2} y_{2} \dots x_{m} y_{m} - 1$ \textbf{String}\;x_1\;y_1\;x_2\;y_2\;\ldots\;x_m\;y_m\;-1
$String$ is the (alphanumeric) name of the country to which the territory belongs. Country names have at least one and no more than twenty characters. If a country has multiple territories, its name appears in each territory's data.
The remaining items specify the vertices: each vertex is given by two non-negative integers, the $x$ - and $y$ -coordinates, separated by a space. No coordinate exceeds $1000$ .
The number of vertices $m$ for each polygon does not exceed $100$ .

The vertices for each territory are listed in order; the territory is formed by connecting each pair of adjacent vertices and also connecting the last vertex to the first. The list of territories for a map ends when all $n$ territories are described.

Polygons are guaranteed to be simple, i.e., their contours do not intersect or touch themselves. No two polygons share a region of non-zero area.

The number of countries in a map does not exceed $10$ .

The input ends with a line containing only a single zero.

Output

For each map, output a single line containing the minimum number of colors required to color the map as described above.

Examples

Example 1