Biome Map
Contest: Kotlin Heroes: Episode 7
Tags: *special, constructive algorithms, dfs and similar, graphs

Polycarp decided to generate a biome map for his game. A map is a matrix divided into cells $$$1 \times 1$$$. Each cell of the map must contain one of the available biomes.

Each biome is defined by two parameters: temperature (an integer from $$$1$$$ to $$$n$$$) and humidity (an integer from $$$1$$$ to $$$m$$$). But not for every temperature/humidity combination, a corresponding biome is available.

The biome map should be generated according to the following rules:

- each cell of the map belongs to exactly one biome;
- each available biome has at least one cell on the map;
- if two cells of the map are adjacent by the side and they belong to biomes with parameters ($$$t_1, h_1$$$) and ($$$t_2, h_2$$$), respectively, then the equality $$$|t_1-t_2| + |h_1-h_2| = 1$$$ holds;
- let the number of available biomes be equal to $$$k$$$, then the number of rows and columns of the map (separately) should not exceed $$$k$$$.

Help Polycarp generate a biome map that meets all the conditions described above (or report that this is impossible).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 20$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10$$$) — maximum temperature and humidity parameters.

The following $$$n$$$ lines contain $$$m$$$ integers each $$$a_{i,1}, a_{i, 2}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 100$$$), where $$$a_{i, j}$$$ — the biome identifier with the parameters $$$(i, j)$$$, if $$$a_{i, j} \neq 0$$$, otherwise the biome with such parameters is not available.

All biome identifiers are different, and there are at least two biomes available.

Output format:
For each test case, print the answer in the following format:

- print $$$-1$$$ in a single line if there is no map that meets all the conditions;
- otherwise, in the first line, print two integers $$$h$$$ and $$$w$$$ — the number of rows and columns of the map, respectively. In the following $$$h$$$ lines, print $$$w$$$ integers — the identifiers of the biomes in the corresponding cells of the map.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
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

Editorial:
Note that if the available biomes do not form a $$$4$$$-connected region (which can be checked with a simple DFS), then the answer is $$$-1$$$, because we will not be able to fulfill either the second rule or the third rule. Otherwise, the answer always exists.
Here is one of the possible constructions. Our map will have a size of $$$k \times k$$$. Such a matrix has $$$2k-1$$$ diagonals, so if we can find a sequence of biomes of length $$$2k-1$$$, such that each biome belongs to the sequence and the third rule is met for any two neighboring biomes in the sequence, then we can fill the matrix by diagonals (the $$$i$$$-th diagonal will be filled with the $$$i$$$-th biome in the sequence). Such a sequence can be obtained by using a DFS traversal, writing out vertices when entering and returning to them.