You are a world-class competitive programmer and a genius problem solver known for your deep understanding of algorithms, data structures, and optimization techniques.

Please solve the following challenging problem:

[Problem Statement
There is a grid with 
H rows and 
W columns. Initially, each integer from 
1 to 
(H×W) is written exactly once in the grid.
Specifically, for 
1≤i≤H and 
1≤j≤W, the cell at the 
i-th row from the top and the 
j-th column from the left contains 
S 
i,j
​
 .
Below, let 
(i,j) denote the cell at the 
i-th row from the top and the 
j-th column from the left.

Determine if it is possible to reach a state where, for all pairs of integers 
(i,j) 
(1≤i≤H,1≤j≤W),
the cell 
(i,j) contains the integer 
((i−1)×W+j) by repeating the following operation at most 
20 times (possibly zero).
If it is possible, print the minimum number of operations required.
If it is impossible in 
20 or fewer operations (including the case where it is impossible no matter how many times the operation is repeated), print 
−1.

Operation: Choose a rectangle of size 
(H−1)×(W−1) from the grid and rotate it 
180 degrees.
More precisely, choose integers 
x and 
y 
(0≤x,y≤1),
and for all pairs of integers 
(i,j) satisfying 
1≤i≤H−1 and 
1≤j≤W−1,
simultaneously replace the integer written in cell 
(i+x,j+y) with the number written in cell 
(H−i+x,W−j+y).

Note that it is only necessary for the integers written in the cells to satisfy the condition; the orientation in which they are written does not matter.

Constraints
3≤H,W≤8
1≤S 
i,j
​
 ≤H×W
If 
(i,j)

=(i 
′
 ,j 
′
 ), then 
S 
i,j
​
 

=S 
i 
′
 ,j 
′
 
​
 
All input values are integers.
Input
The input is given from Standard Input in the following format:

H 
W
S 
1,1
​
  
S 
1,2
​
  
… 
S 
1,W
​
 
S 
2,1
​
  
S 
2,2
​
  
… 
S 
2,W
​
 
⋮
S 
H,1
​
  
S 
H,2
​
  
… 
S 
H,W
​
 
Output
Print the minimum number of operations required to meet the conditions of the problem statement.
If it is impossible to satisfy the conditions with 
20 or fewer operations, output 
−1.

Sample Input 1
Copy
3 3
9 4 3
2 1 8
7 6 5
Sample Output 1
Copy
2
Operating in the following order will satisfy the conditions of the problem statement in 
2 operations.

Operate by choosing the rectangle in the top-left corner. That is, by choosing 
x=0 and 
y=0.
Operate by choosing the rectangle in the bottom-right corner. That is, by choosing 
x=1 and 
y=1.
On the other hand, it is impossible to satisfy the conditions with one or fewer operations, so print 
2.



Sample Input 2
Copy
4 6
15 18 1 14 3 4
23 24 19 8 9 12
13 2 17 6 5 16
21 22 7 20 11 10
Sample Output 2
Copy
-1
It is impossible to satisfy the conditions with 
20 or fewer operations, so print 
−1.

Sample Input 3
Copy
4 6
1 4 13 16 15 18
21 20 9 12 23 10
17 14 5 6 3 2
11 22 7 24 19 8
Sample Output 3
Copy
20
Sample Input 4
Copy
4 3
1 2 3
4 5 6
7 8 9
10 11 12
Sample Output 4
Copy
0


]

Approach this problem by:

Understanding the Problem Thoroughly:
Carefully read and interpret the problem statement.
Identify and explain the core challenges and constraints.
Discuss any potential ambiguities or areas that require special attention.
Considering Diverse Perspectives:
Explore multiple methodologies to tackle the problem (e.g., brute-force, greedy algorithms, dynamic programming, divide and conquer, graph algorithms, advanced data structures, mathematical approaches).
Evaluate the pros and cons of each potential approach.
Consider both traditional and unconventional methods that could lead to an optimal solution.
Developing an Optimal Solution:
Select the most promising approach based on efficiency and feasibility.
Provide a step-by-step explanation of your reasoning and solution strategy.
Discuss how you address edge cases and adhere to the problem's constraints.
Optimize your solution for both time and space complexity, explaining any trade-offs made.
Demonstrating the Solution:
Write clean, well-documented code in the programming language of your choice.
Include comments to explain critical sections of the code.
Ensure the code is readable, efficient, and follows best coding practices.
Testing and Validation:
Create sample test cases, including edge cases, to validate your solution.
Show the expected output for each test case.
Explain how you would perform further testing to ensure the solution's robustness.
Reflecting on the Solution:
Summarize what makes your solution effective.
Discuss any insights or clever techniques used.
Mention possible alternatives and why they may not be as effective.
Please provide your comprehensive solution and explanation, showcasing your exceptional problem-solving skills and depth of knowledge.