B. Три семёрки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лотерея «Три Семёрки» проводилась $$$m$$$ дней. В день $$$i$$$ в лотерее участвовали $$$n_i$$$ людей с номерами $$$a_{i, 1}, \ldots, a_{i, n_i}$$$.

Известно, что в каждый из $$$m$$$ дней из участников лотереи выбирался ровно один победитель. Победителю лотереи в день $$$i$$$ запрещено участвовать в лотерее в дни с номерами от $$$i+1$$$ до $$$m$$$.

К сожалению, информация о победителях лотереи была утеряна. Вам нужно восстановить любой возможный список победителей лотереи в дни с номерами от $$$1$$$ до $$$m$$$ или определить, что это невозможно.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$m$$$ ($$$1 \le m \le 50\,000$$$) — количество дней, в которые проводилась лотерея.

Далее для каждого $$$i$$$ от $$$1$$$ до $$$m$$$ находится блок данных из двух строк.

В первой строке каждого блока находится одно целое число $$$n_i$$$ ($$$1 \le n_i \le 50\,000$$$) — количество участников лотереи в день $$$i$$$.

Во второй строке блока находятся числа $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ ($$$1 \le a_{i, j} \le 50\,000$$$) — номера участников лотереи в день $$$i$$$. Гарантируется, что все числа $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ попарно различны.

Гарантируется, что сумма значений $$$n_i$$$ по всем блокам всех наборов входных данных не превосходит $$$50\,000$$$.

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

Для каждого набора входных данных, если решения не существует, выведите одно целое число $$$-1$$$.

Иначе выведите $$$m$$$ целых чисел $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \le p_i \le 50\,000$$$) — номера победителей лотереи в дни с $$$1$$$ по $$$m$$$. Если существует несколько корректных решений, выведите любое из них.

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

В первом наборе входных данных один из подходящих ответов $$$[8, 2, 1]$$$, так как участник с номером $$$8$$$ участвовал в день $$$1$$$, но не участвовал в дни $$$2$$$ и $$$3$$$; участник с номером $$$2$$$ участвовал в день $$$2$$$, но не участвовал в день $$$3$$$; а участник с номером $$$1$$$ участвовал в день $$$3$$$. Обратите внимание, что это не единственный возможный ответ, например, $$$[8, 9, 4]$$$ также является верным ответом.

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

В третьем наборе входных данных в дни $$$2$$$, $$$3$$$ и $$$4$$$ участвовал только один участник, а в день $$$1$$$ единственный участник, не участвовавший в лотерее в днях $$$2, 3, 4$$$ — это участник $$$2$$$. Значит $$$[2, 1, 4, 3]$$$ — единственно верный ответ.