|
Собери сам
(Время: 3 сек. Память: 16 Мб Сложность: 79%)
Компания «Ёжики-Хрюшечки» готовит новый конструктор «Собери сам» для детей младшего школьного возраста. Одна из главных составных частей конструктора – электронное устройство, для работы которого надо соединить набор клемм на специальной доске проводами.
Провода, которыми требуется выполнить соединение, имеют топологическую структуру дерева, в вершинах которого расположены контакты, подключаемые к клеммам. В свою очередь, доска имеет изображенную на ней схему укладки проводов, поэтому на первый взгляд кажется, что подключить устройство очень просто. Однако, к сожалению, все контакты на проводах, кроме одного выделенного, подключаемого к «корню» дерева, одинаковые, поэтому понять какой контакт куда подключить непросто.
Например, рассмотрим изображенную на рисунке схему.
На этой схеме возможны два способа подключить провода, они показаны на следующем рисунке.
Разработчики из компании «Ёжики-Хрюшечки» не хотят, чтобы у схемы было несколько возможных подключений. Конечно, можно было бы пометить каждый контакт и каждую клемму уникальным кодом, чтобы ясно было что куда надо подключить, но тогда игра получилась бы не слишком интересной. Поэтому они решили раскрасить клеммы и контакты в разные цвета, так, чтобы были выполнены следующие условия:
- контакт и клемма, которые необходимо соединить, раскрашены в один цвет;
- существует ровно один способ соединить контакты и клеммы, чтобы не каждый контакт был соединен с клеммой того же цвета, провода проходили вдоль соответствующих линий на схеме и выделенный контакт соединялся с выделенной клеммой в корне дерева.
Разумеется, разработчики хотели бы использовать по возможности меньшее число цветов. Например, для схемы, изображенной на рисунке выше, достаточно двух цветов:
По заданному дереву проводов определите, в какое минимальное число цветов его можно раскрасить, чтобы выполнить приведенные условия.
Входные данные
Первая строка входного файла INPUT.TXT содержит число n – количество вершин дерева (1 ≤ n ≤ 500). Пусть вершины дерева пронумерованы числами от 1 до n, так что номер родителя вершины меньше ее номера. Корень дерева имеет номер 1. Вторая строка входного файла содержит n-1 число, для каждой вершины, начиная со второй, указан номер ее родителя.
Выходные данные
Первая строка выходного файла OUTPUT.TXT должна содержать число k – минимальное необходимое количество цветов. Следующая строка должна содержать n целых чисел – цвета вершин.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 9
1 2 2 4 1 6 7 6 | 2
1 1 1 1 1 2 1 1 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
