C. Престановка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность из $$$n$$$ чисел называется перестановкой, если она содержит в себе все числа от $$$1$$$ до $$$n$$$ ровно по одному разу. Например, последовательности [$$$3, 1, 4, 2$$$], [$$$1$$$] и [$$$2,1$$$] являются перестановками, а [$$$1,2,1$$$], [$$$0,1$$$] и [$$$1,3,4$$$] — нет.

У Кристины была перестановка $$$p$$$ из $$$n$$$ элементов. Она записала ее на доску $$$n$$$ раз таким образом, что:

  • записывая перестановку в $$$i$$$-й ($$$1 \le i \le n)$$$ раз она пропускала элемент $$$p_i$$$
Таким образом, всего она записала на доску $$$n$$$ последовательностей длины $$$n-1$$$ каждая.

Например, пусть у Кристины была перестановка $$$p$$$ = $$$[4,2,1,3]$$$ длины $$$4$$$. Тогда она сделала следующее:

  1. Записала на доску последовательность $$$[2, 1, 3]$$$, пропустив элемент $$$p_1=4$$$ из исходной перестановки.
  2. Записала на доску последовательность $$$[4, 1, 3]$$$, пропустив элемент $$$p_2=2$$$ из исходной перестановки.
  3. Записала на доску последовательность $$$[4, 2, 3]$$$, пропустив элемент $$$p_3=1$$$ из исходной перестановки.
  4. Записала на доску последовательность $$$[4, 2, 1]$$$, пропустив элемент $$$p_4=3$$$ из исходной перестановки.

Вам известны $$$n$$$ последовательностей, которые были записаны на доску, но Вы не знаете, в каком порядке они были записаны. Восстановите по ним исходную перестановку.

Таким образом, если Вам известны последовательности $$$[4, 2, 1]$$$, $$$[4, 2, 3]$$$, $$$[2, 1, 3]$$$, $$$[4, 1, 3]$$$, то исходная перестановка будет равна $$$p$$$ = $$$[4, 2, 1, 3]$$$.

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

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$3 \le n \le 100$$$).

Затем следует $$$n$$$ строк, каждая из которых содержит ровно $$$n-1$$$ целое число и описывает одну из последовательностей, выписанных на доску.

Гарантируется, что все последовательности могли быть получены из некоторой перестановки $$$p$$$, а также что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите в отдельной строке перестановку $$$p$$$ такую, что из нее могли быть получены заданные $$$n$$$ последовательностей.

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

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

Первый набор входных данных разобран в условии задачи.

Во втором наборе входных данных последовательности выписаны в правильном порядке.