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