0155. Восстановление дерева

Input file name:	tree.in
Output file name:	tree.out
Time limit:	2 s
Memory limit:	32 megabytes

Известно, что существует всего n^(n-2) деревьев с пронумерованными вершинами (от 1 до n). Доказательство этого базируется на представлении дерева в виде набора из n-2 чисел от 1 до n, который строится следующим образом:

1. Выбираем висячую вершину с минимальным номером k.
2. Выбрасываем эту вершину и ребро, на котором она висит (k,l). Записываем номер вершины l, на которой висела k.
3. Если осталось более двух вершин, то повторяем процесс.

Например, пусть есть дерево из 5 вершин: (1,2), (1,5), (3,1), (3,4). В первый раз будет выбрана вершина 2, а записано число 1, далее выбираем 4 и записываем 3, Последней удаляется 3 и записывается снова 1. Утверждается, что по коду можно однозначно восстановить дерево. Ваша задача √ это сделать.

Формат входного файла

Во входном файле на первой строке количество наборов входных данных M. В первой строке каждого набора - число 2 ≤ n ≤ 1000000. Далее n-2 строки, каждая из которых содержит одно число Ki - число, записанное на i-м шаге.

Формат выходного файла

Для каждого набора следует вывести n-1 строку - рёбра искомого дерева в произвольном порядке. Вывод для различных наборов разделять пустой строкой. Гарантируется, что сумма значений n из всех наборов не превосходит 1000000.

Пример:

tree.in	tree.out
2 3 2 5 1 3 1	1 2 2 3 1 2 1 3 1 5 3 4

Source: Petrozavodsk Summer 2003. Petrozavodsk SU Contest #2, Friday, August 29

Discuss       Submit a solution



Printable version