#P2756. [SCOI2012]奇怪的游戏

    ID: 1862 传统题 4000ms 512MiB 尝试: 5748 已通过: 1040 难度: 8 上传者: 标签>CF2400提高+/省选-不变量分析二分图建模二分答案Dinic最大流最小割定理

[SCOI2012]奇怪的游戏

题目描述

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

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

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

输入格式

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

每轮游戏的第一行有两个整数 NN 和 MM,分别代表棋盘的行数和列数。 接下来有 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

提示

对于 30%30\% 的数据,保证 T≤10,1≤N,M≤8 T\le 10,1\le N,M \le 8。 对于 100%100\% 的数据,保证 T≤10,1≤N,M≤40T \le 10,1 \le N,M\le 40,所有数为正整数且小于 10910^9。