ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1069. Код Прюфера

Ограничение времени: 0.25 секунды
Ограничение памяти: 8 МБ
Пусть имеется дерево (т.е. связный граф без циклов) с N вершинами, занумерованными числами от 1 до N (N ≥ 2). Код Прюфера для этого дерева строится следующим образом: из всех висячих вершин (т.е. из вершин, смежных в точности одному ребру) выбирается вершина с наименьшим номером. Затем эта вершина и смежное ей ребро удаляются из графа, а номер вершины, с которой она была смежной, записывается. В полученном графе снова выбирается висячая вершина с наименьшим номером, удаляется, и так повторяется до тех пор, пока не останется всего одна вершина. Очевидно, что в результате останется единственная вершина с номером N. Выписанный набор чисел (N−1 число, каждое в пределах от 1 до N) называется кодом Прюфера данного графа.
Ваша задача — по заданному коду Прюфера восстановить дерево, т.е. найти списки смежности его вершин.
Предполагается, что 2 ≤ N ≤ 7500.

Исходные данные

На входе программа получает набор чисел — код Прюфера некоторого дерева. Числа разделены пробелами и/или переводами строк.

Результат

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

Пример

исходные данныерезультат
2 1 6 2 6
1: 4 6
2: 3 5 6
3: 2
4: 1
5: 2
6: 1 2
Автор задачи: Магаз Асанов
Источник задачи: Ural State Univerisity Personal Contest Online February'2001 Students Session