Розподіл каналів
Коли радіостанція веде мовлення на великих територіях, для того, щоб кожен слухач мав сильний сигнал, використовують ретранслятори. Тим не менше, канали для кожного ретранслятора повинні бути ретельно підібрані, щоб сусідні ретранслятори не заважали один одному, а це можливо лише тоді, коли сусідні ретранслятори використовують різні канали.
Оскільки радіочастотний спектр є цінним ресурсом, то число каналів для заданої мережі потрібно мінімізувати. Ви повинні написати програму, яка зчитує опис мережі ретрансляторів і визначає кількість каналів, які потрібно для цієї мережі.
Вхідні дані
Вхідні дані містять описи декількох мереж. Кожен опис розпочинається з рядка, що містить число ретрансляторів у мережі – число від 1 до 26. Усі ретранслятори позначаються великими латинськими буквами. Наприклад, якщо у мережі десять ретрансляторів, то вони мають позначення – A, B, C, .., I, J. Вхідні дані завершуються мережею, що не містить ретрансляторів. Цю мережу не потрібно опрацьовувати.
Після кількості ретрансляторів іде список суміжних ретрансляторів. Кожен рядок має вигляд:
A:BCDH
Опис показує, що ретранслятори B, C, D, H межують з ретранслятором A. Перший рядок описує, які ретранслятори суміжні з A, другий рядок описує, які ретранслятори суміжні з B і так далі. Якщо ретранслятор не має суміжних, то він описується так:
A:
Усі ретранслятори подано у алфавітному порядку.
Якщо A межує з B, то B обов’язково межує з A. Крім того, оскільки ретранслятори лежать в одній площині, то граф утворений шляхом з’єднання сусідніх ретрансляторів не має ребер, які перетинаються.
Вихідні дані
Для кожного опису мережі (за винятком останньої, яка не опрацьовується), виведіть єдиний рядок, який містить мінімальну кількість каналів, яку необхідно мати, щоб сусідні канали не заважали один одному. Формат рядка показано у прикладі вихідних даних. Подбайте про те, щоб граматично вірно вивести повідомлення, коли канал лише один.