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

Ваша задача — по заданному коду Прюфера восстановить дерево, т.е. найти списки смежности его вершин.

Предполагается, что 2 ≤ N ≤ 7500.

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

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