• Код Прюфера
    KODPRUF

Пусть имеется дерево (т.е. связный граф без циклов) с N вершинами (1<N<7501).
Ваша задача - по заданному коду Прюфера восстановить дерево, т.е. найти списки смежности для каждой из вершин.

Технические условия:

Вход: на входе программе дается набор чисел, соответствующий коду Прюфера некоторого дерева. Числа разделены пробелами.

Выход: на выходе программа должна построить списки смежности вершин восстановленного по коду графа. Списки смежности для вершин выводятся в порядке номеров вершин. Список смежности вершины должен иметь следующий формат: номер вершины, двоеточие, пробел, и далее номера смежных вершин через пробел. Вершины в списке должны быть отсортированы по возрастанию номеров.

Пример:

KODPRUF.DAT
2 1 6 2 6

KODPRUF.SOL
1: 4 6
2: 3 5 6
3: 2
4: 1
5: 2
6: 1 2