Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Собери сам

(Время: 3 сек. Память: 16 Мб Сложность: 79%)

Компания «Ёжики-Хрюшечки» готовит новый конструктор «Собери сам» для детей младшего школьного возраста. Одна из главных составных частей конструктора – электронное устройство, для работы которого надо соединить набор клемм на специальной доске проводами.

Провода, которыми требуется выполнить соединение, имеют топологическую структуру дерева, в вершинах которого расположены контакты, подключаемые к клеммам. В свою очередь, доска имеет изображенную на ней схему укладки проводов, поэтому на первый взгляд кажется, что подключить устройство очень просто. Однако, к сожалению, все контакты на проводах, кроме одного выделенного, подключаемого к «корню» дерева, одинаковые, поэтому понять какой контакт куда подключить непросто.

Например, рассмотрим изображенную на рисунке схему.

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

Разработчики из компании «Ёжики-Хрюшечки» не хотят, чтобы у схемы было несколько возможных подключений. Конечно, можно было бы пометить каждый контакт и каждую клемму уникальным кодом, чтобы ясно было что куда надо подключить, но тогда игра получилась бы не слишком интересной. Поэтому они решили раскрасить клеммы и контакты в разные цвета, так, чтобы были выполнены следующие условия:

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

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

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

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

Первая строка входного файла INPUT.TXT содержит число n – количество вершин дерева (1 ≤ n ≤ 500). Пусть вершины дерева пронумерованы числами от 1 до n, так что номер родителя вершины меньше ее номера. Корень дерева имеет номер 1. Вторая строка входного файла содержит n-1 число, для каждой вершины, начиная со второй, указан номер ее родителя.

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

Первая строка выходного файла OUTPUT.TXT должна содержать число k – минимальное необходимое количество цветов. Следующая строка должна содержать n целых чисел – цвета вершин.

Пример

INPUT.TXTOUTPUT.TXT
19
1 2 2 4 1 6 7 6
2
1 1 1 1 1 2 1 1 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ