F. Восстановить перестановку по отсортированным отрезкам
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мы загадали перестановку $$$p$$$, состоящую из $$$n$$$ целых чисел. Перестановкой длины $$$n$$$ называется массив длины $$$n$$$, где каждый элемент от $$$1$$$ до $$$n$$$ встречается ровно один раз. Эта перестановка вам неизвестна.

Для каждой позиции $$$r$$$ от $$$2$$$ до $$$n$$$ мы выбрали некоторый другой индекс $$$l$$$ ($$$l < r$$$) и дали вам отрезок $$$p_l, p_{l + 1}, \dots, p_r$$$ в отсортированном порядке (то есть мы переставили элементы на этом отрезке так, что элементы на этом отрезке оказались отсортированными). Таким образом, вам задан ровно $$$n-1$$$ отрезок первоначальной перестановки, но элементы внутри каждого отрезка отсортированы. Отрезки даны вам в случайном порядке.

Например, если загаданная перестановка — $$$p=[3, 1, 4, 6, 2, 5]$$$, то возможное заданное множество отрезков:

  • $$$[2, 5, 6]$$$
  • $$$[4, 6]$$$
  • $$$[1, 3, 4]$$$
  • $$$[1, 3]$$$
  • $$$[1, 2, 4, 6]$$$

Ваша задача — найти любую подходящую перестановку (то есть любую перестановку, соответствующую входным данным). Гарантируется, что входные данные соответствуют некоторой перестановке (то есть перестановка существует).

Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 200$$$) — длину перестановки.

Следующая $$$n-1$$$ строка описывает заданные отрезки.

$$$i$$$-я строка содержит описание $$$i$$$-го отрезка. Строка начинается с числа $$$k_i$$$ ($$$2 \le k_i \le n$$$) — длины $$$i$$$-го отрезка. Затем следуют $$$k_i$$$ целых чисел. Все числа в строке различны, отсортированы по возрастанию, между $$$1$$$ и $$$n$$$, включительно.

Гарантируется, что искомая перестановка $$$p$$$ существует для каждого набора тестовых данных.

Также гарантируется, что сумма чисел $$$n$$$ по всем наборам тестовых данных не превосходит $$$200$$$ ($$$\sum n \le 200$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ: $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ должны быть различны) — любую подходящую перестановку (то есть любую перестановку, удовлетворяющую входным данным набора тестовых данных).

Пример
Входные данные
5
6
3 2 5 6
2 4 6
3 1 3 4
2 1 3
4 1 2 4 6
5
2 2 3
2 1 2
2 1 4
2 4 5
7
3 1 2 6
4 1 3 5 6
2 1 2
3 4 5 7
6 1 2 3 4 5 6
3 1 3 6
2
2 1 2
5
2 2 5
3 2 3 5
4 2 3 4 5
5 1 2 3 4 5
Выходные данные
3 1 4 6 2 5 
3 2 1 4 5 
2 1 6 3 5 4 7 
1 2 
2 5 3 4 1