Ви були досить везучими, щоб отримати карту при вході у легендарний таємничий чарівний світ. На карті показано усі території запланованого дослідження, у тому числі ряд країн зі складними кордонами. Карта чітко прорисована, але сірими чорнилами, і тому важко з поршого погляду визначити, яка область належить до якої країни, а це може призвести вас до серйозних наслідків. Ви вирішили розфарбувати карту перед тим як поринути у таємничий світ. "Багато залежить від підготовки", не раз ви казали собі.
Кожна країна має одну чи декілька територій, кожна з яких має полігональну форму. Території, які належать одній країні можуть дотикатись, а можуть і не дотикатись одна до одної, тобто можуть бути роз'єднані території. Усім територіям, які належать одній і тій же країні, потріьно надати один і той же колір. Більше того, ви можете надати один колір і більше ніж одній країні, але, щоб уникнути плутаниці, двом сусіднім різним країнам потрібно надати різні кольори. Дві країни вважаються сусідніми, якщо довільною частиною своїх територій мають спільну границю ненульової довжини.
Напишіть програму, яка знаходить найменшу кількість кольорів, необхідних для розфарбування карти.
Вхідні дані складаються з декількох картографічних даних. Кожна задана карта починається з рядка, який містить загальну кількість територій n, після чого дані для цих територій. n - натуральне число, не більше за 100. Дані про території з m вершин мають наступний формат:
String x1 y1 x2 y2 : : : xm ym -1
"String" (послідовність алфавітно-цифрових символів) задає назву країни, якій він належить. Назва країни має по меншій мірі один символ і ніколи не буде більше двадцяти. Коли у країні є декілька територій, її ім'я з'явиться у кожному з її описів.
Інші рядки задають вершини території. Вершина у рядку даних подається парою невід'ємних цілих чисел, які задають х- та у-координати вершини. х- та у-координати відокремлено пропуском, і після у-координати відразу йде переведення рядка. Границі кожної території отримуються шляхом з'єднання сусідніх вершин, а також першої та останньої вершини. Жодна з х- та у-координат не перевищує 1000. Єдине число -1 у рядку означає завершення перерахування вершин. Кількість вершин m не перевищує 100.
Можно вважати, що контури полігонів прості, тобто вони не перетинаються і дотикаються самі до себе. Немає двох многокутників, які розділяють області ненульової площі. Кількість країн на карті не перевищує 10.
Завершенням опису є рядок, який містить лише нуль і позначає завершення вхідних даних.
Для кожної заданої карти вивести у окремому рядку найменшу кількість кольорів, необхідни для розфарбування чергової карти, яка задовольняє заданим умовам.