Кольорова карта#3201

Кольорова карта

1 секунда

64 мегабайти

Середня

Вам пощастило отримати карту саме перед входом до легендарного чарівного загадкового світу. Карта зображає всю територію вашого майбутнього дослідження, включаючи кілька країн зі складними кордонами. Карта чітко намальована, але лише сепією; складно швидко визначити, яка область належить якій країні, і це може поставити вас у серйозну небезпеку. Ви вирішуєте розфарбувати карту перед входом на територію. «Багато що залежить від підготовки», — кажете ви собі.

Кожна країна має одну або більше територій, кожна з яких є полігоном. Території, які належать до однієї країни, можуть межувати між собою або бути відокремленими — тобто країна може мати не поєднані території. Усі території, що належать одній країні, повинні бути забарвлені одним кольором. Можна використовувати один і той самий колір для кількох країн, але щоб уникнути плутанини, будь-які дві «сусідні» країни мають бути пофарбовані в різні кольори. Дві країни вважаються «сусідніми», якщо будь-які їхні території мають спільний кордон ненульової довжини.

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

Вхідні дані

Вхід складається з кількох описів карт. Кожна карта починається з рядка, що містить загальну кількість територій $n$ , після чого йде опис кожної території. $n$ — додатне ціле число, що не перевищує $100$ .

Дані про територію з $m$ вершинами подаються так:

Перший елемент: $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$ — (буквено-цифрова) назва країни, до якої належить територія. Назви країн мають як мінімум один і не більше двадцяти символів. Якщо у країни кілька територій, її ім'я зустрічається у даних кожної з них.
Наступні елементи — це координати вершин: кожна вершина задається двома невід'ємними цілими числами — $x$ та $y$ -координатами, розділеними пробілом. Жодна координата не перевищує $1000$ .
Кількість вершин $m$ для кожного полігону не перевищує $100$ .

Вершини для кожної території перелічені по порядку; територія утворюється шляхом з'єднання кожної пари сусідніх вершин і з'єднанням останньої вершини з першою. Перелік територій для однієї карти закінчується після опису всіх $n$ територій.

Гарантується, що полігони прості — тобто їхні контури не перетинаються і не торкаються самі себе. Жодні два полігони не мають спільної області з ненульовою площею.

Кількість країн на одній карті не перевищує $10$ .

Ввід закінчується рядком, що містить лише один нуль.

Вихідні дані

Для кожної карти виведіть один рядок, що містить найменшу кількість кольорів, необхідну для розфарбування карти, як описано вище.

Приклади

Приклад 1