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

Поликарп решил сгенерировать карту биомов для своей игры. Карта представляет собой матрицу, разбитую на клетки $$$1 \times 1$$$. В каждой клетке карты должен находиться один из доступных биомов.

Каждый биом определяется двумя параметрами: температура (целое число от $$$1$$$ до $$$n$$$) и влажность (целое число от $$$1$$$ до $$$m$$$). Но, возможно, не для каждой комбинации температура/влажность доступен соответствующий биом.

Карта биомов должна быть сгенерирована по следующим правилам:

  • каждая клетка карты принадлежит ровно одному биому;
  • каждому доступному биому принадлежит хотя бы одна клетка карты;
  • если две клетки карты являются соседними по стороне, и они принадлежат биомам с параметрами ($$$t_1, h_1$$$) и ($$$t_2, h_2$$$) соответственно, то должно выполняться равенство $$$|t_1-t_2| + |h_1-h_2| = 1$$$;
  • пусть количество доступных биомов равно $$$k$$$. Ни количество строк, ни столбцов карты не должно превышать $$$k$$$.

Помогите Поликарпу сгенерировать карту биомов, которая удовлетворяет всем вышеописанным условиям (или сообщите, что это невозможно).

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

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

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

Следующие $$$n$$$ строк содержат по $$$m$$$ целых чисел $$$a_{i,1}, a_{i, 2}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 100$$$), где $$$a_{i, j}$$$ — идентификатор биома с параметрами $$$(i, j)$$$, если $$$a_{i, j} \neq 0$$$, иначе биом с такими параметрами недоступен.

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

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

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

  • в единственной строке выведите $$$-1$$$, если не существует карты удовлетворяющей всем условиям;
  • иначе в первой строке выведите два целых числа $$$h$$$ и $$$w$$$ — количество строк и столбцов карты соответственно. В следующих $$$h$$$ строках выведите по $$$w$$$ целых чисел — идентификаторы биомов в соответствующих клетках поля.
Пример
Входные данные
4
2 3
0 2 5
0 1 0
3 5
0 3 4 9 11
1 5 0 10 12
0 6 7 0 0
2 2
2 0
0 5
1 2
13 37
Выходные данные
1 3
5 2 1 
2 8
11 9 4 3 5 1 5 6 
12 10 9 4 3 5 6 7 
-1
1 2
13 37