Задача E. Implicit array

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Отсортированный массив целых чисел задан неявным образом. Вместо каждого элемента известно множество, состоящее из данного элемента и его соседей справа и слева. У первого и последнего элемента есть не более одного соседа. Заметим, что множество не сохраняет ни порядок элементов, ни наличие дубликатов.

Напишите программу, которая восстановит массив в явном виде (все элементы по порядку).

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

Первая строка входного файла содержит целое число N — количество элементов в массиве.

Следующие N строк содержат неявные описания элементов массива: размер множества si и si различных целых чисел aij — множество, состоящее из i-го элемента массива и его соседей.

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

Выходной файл должен содержать N целых чисел — элементы исходного отсортированного массива.

Ограничения

1 ≤ N ≤ 105

 − 109 ≤ aij ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7
1 1
1 1
2 1 2
2 1 2
2 2 3
2 2 3
1 3
1 1 1 2 2 3 3
2
1
1 7
7

0.163s 0.025s 15