Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

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

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

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483