#180. 2756. [SCOI2012]奇怪的游戏

2756. [SCOI2012]奇怪的游戏

[SCOI2012] 奇怪的游戏

题目描述

BlinkerBlinker最近喜欢上一个奇怪的游戏。

这个游戏在一个 N×MN \times M 的棋盘上玩,每个格子有一个数。每次BlinkerBlinker会选择两个相邻的格子,并使这两个数都加上11

现在BlinkerBlinker想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同一个数则输出1-1

输入格式

输入的第一行是一个整数TT,表示输入数据有T轮游戏组成。

每轮游戏的第一行有两个整数NNMM, 分别代表棋盘的行数和列数。 接下来有NN行,每行MM个数。

输出格式

对于每个游戏输出最少能使游戏结束的次数,如果永远不能变成同一个数则输出1-1

样例 #1

样例输入 #1

2 
2 2 
1 2 
2 3 
3 3 
1 2 3 
2 3 4 
4 3 2

样例输出 #1

2 
-1

提示

对于3030%的数据,保证T<=10,1<=N,M<=8 T<=10,1<=N,M<=8

对于100100%的数据,保证 T<=10,1<=N,M<=40T<=10,1<=N,M<=40,所有数为正整数且小于10000000001000000000