← 返回题目列表

Codeforces · 1533/G

G. 生物群落地图

中文机器翻译题面 查看原题

Polycarp 决定为他的游戏生成一张生物群落地图。地图是一个分为单元格 $$$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$$$。

帮助 Polycarp 生成满足上述所有条件的生物群落地图(或报告这是不可能的)。

输入

第一行包含一个整数 $$$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$$$ 整数 - 地图相应单元格中生物群落的标识符。

示例

输入 #1

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

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