Цветная карта

Вы были достаточно удачливы, чтобы заполучить карту при входе в легендарный таинственный волшебный мир. На карте показаны всей территории планируемого исследования, в том числе ряд стран со сложными границами. Карта четко нарисована, но серыми чернилами, и поэтому трудно определить с первого взгляда, какая область принадлежит к какой стране, а это может привести вас к серьезным последствиям. Вы решили раскрасить карту перед тем как шагнуть в таинственный мир. "Многое зависит от подготовки", не раз вы говорили себе.

Каждая страна имеет одну или несколько территорий, каждая из которых имеет полигональную форму. Территории, принадлежащие одной стране могут прикасаться, а могут и не прикасаться друг к другу, то есть могут быть разъединённые территории. Всем территориям, принадлежащим к одной и той же стране, должен быть присвоен один и тот же цвет. Более того, вы можете назначить один цвет и более чем одной стране, но, чтобы избежать путаницы, двум соседним разным странам должны быть назначены разные цвета. Две страны считаются соседними, если любой частью своих территорий имеют общую границу ненулевой длины.

Напишите программу, которая находит наименьшее количество цветов, необходимых для раскраски карты.

Входные данные

Входные данные состоят из нескольких картографических данных. Каждая заданная карта начинается со строки, содержащей общее количество территорий n, после чего данные для этих территорий. n - натуральное число, не большее, чем 100. Данные о территории из m вершин имеют следующий формат:

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

"String" (последовательность алфавитно-цифровых символов) дает название страны, которой он принадлежит. Название страны имеет по крайней мере один символ и никогда не будет более двадцати. Когда в стране есть несколько территорий, её имя появится в каждом из её описаний.

Остальные строки представляют собой вершины территории. Вершина в строке передачи данных есть пара неотрицательных целых чисел, которые представляют х- и у-координаты вершины. х- и у-координаты разделены пробелом, и после у-координаты сразу идёт перевод строки. Границы каждой территории получаются путем соединения соседних вершин, а также первой и последней вершины. Ни одна из х- и у-координат не превышает 1000. Единственное число -1 в строке означает окончание перечисления вершин. Количество вершин m не превышает 100.

Можно считать, что контуры полигонов простые, то есть они не пересекаются и не касаются сами к себе. Нет двух многоугольников, которые разделяют области ненулевой площади. Количество стран на карте не превышает 10.

Завершением описания является строка, содержащая только ноль, означающая окончание входных данных.

Выходные данные

Для каждой заданной карты вывести в отдельной строке наименьшее количество цветов, необходимых для раскраски очередной карты, удовлетворяющих заданным условиям.