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

$$$n$$$ коров Фермера Джона играют в карточную игру! У Фермера Джона есть колода из $$$n \cdot m$$$ карт, пронумерованных от $$$0$$$ до $$$n \cdot m-1$$$. Он раздает $$$m$$$ карт каждой из своих $$$n$$$ коров.

Фермер Джон хочет, чтобы игра была честной, поэтому каждая корова может сыграть только $$$1$$$ карту за раунд. Он решает определить порядок ходов, который задается перестановкой$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$, так что корова с номером $$$p_i$$$ будет $$$i$$$-й коровой, которая положит карту наверх центральной стопки в раунде.

Другими словами, в каждом раунде происходят следующие события:

  • Корова с номером $$$p_1$$$ кладет любую карту из своей колоды наверх центральной стопки.
  • Корова с номером $$$p_2$$$ кладет любую карту из своей колоды наверх центральной стопки.
  • ...
  • Корова с номером $$$p_n$$$ кладет любую карту из своей колоды наверх центральной стопки.

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

Фермер Джон задается вопросом: существует ли $$$p$$$, такое что все его коровы смогут опустошить свою колоду после игры во все $$$m$$$ раундов? Если да, выведите любое допустимое $$$p$$$. В противном случае выведите $$$-1$$$.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ содержит каждое целое число от $$$1$$$ до $$$n$$$ ровно один раз

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

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

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \cdot m \leq 2\,000$$$) — количество коров и количество карт, которые получает каждая корова.

Следующие $$$n$$$ строк содержат по $$$m$$$ целых чисел каждая — карты, полученные каждой коровой. Гарантируется, что все указанные числа (по всем $$$n$$$ строкам) различны и находятся в диапазоне от $$$0$$$ до $$$n \cdot m - 1$$$, включительно.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$2\,000$$$.

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

Для каждого набора входных данных выведите следующее на новой строке:

  • Если $$$p$$$ существует, выведите $$$n$$$ целых числа, разделенных пробелами: $$$p_1, p_2, \ldots, p_n$$$.
  • В противном случае выведите $$$-1$$$.
Пример
Входные данные
4
2 3
0 4 2
1 5 3
1 1
0
2 2
1 2
0 3
4 1
1
2
0
3
Выходные данные
1 2
1
-1
3 1 2 4
Примечание

В первом примере один из порядков ходов, который позволяет сыграть все карты, заключается в том, чтобы первой корове ходить перед второй коровой. Карты, которые будут сыграны: $$$0\rightarrow1\rightarrow2\rightarrow3\rightarrow4\rightarrow5$$$.

Во втором примере только одна корова, поэтому если корова сыграет все свои карты в порядке возрастания, колода будет опустошена.

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