The state of grid A can be represented by a pair \((P, Q)\), where \(P = (P_1, P_2, \ldots, P_H)\) is a permutation representing the original position of the \(i\)-th row, and \(Q = (Q_1,Q_2, \ldots, Q_W)\) is a permutation representing the original position of the \(j\)-th column,

Initially, \(P = (1, 2, \ldots, H)\) and \(Q = (1, 2, \ldots, W)\); swapping adjacent rows or columns corresponds to swapping two adjacent elements in \(P\) or \(Q\), respectively. Also, the integer written on square \((i, j)\) in the current grid can be obtained as the integer written on square \((i, j)\) in the original state.

For example, in the process in Sample Input / Output 1, state \((P, Q)\) changes as

\[ \begin{aligned} &P = (1, 2, 3, 4), Q = (1, 2, 3, 4, 5)\\ \rightarrow &P = (1, 2, 3, 4), Q = (1, 2, 3, 5, 4)\\ \rightarrow &P = (1, 3, 2, 4), Q = (1, 2, 3, 5, 4)\\ \rightarrow &P = (1, 3, 2, 4), Q = (1, 3, 2, 5, 4).\\ \end{aligned} \]

The total number of states is the product of the number of possible \(P\) (\(H!\) permutations of \((1, 2, \ldots, H)\)) and that of possible \(Q\) (\(W!\) permutations of \((1, 2, \ldots, W)\)), so it is \(H!W! \leq 5!\times 5! = 14400\), small enough to get the answer to this problem within the execution tie limit.

So we perform the following operation for each of the \(H!W!\) pairs \((P, Q)\) of a permutation \(P\) of \((1, 2, \ldots, H)\) and a permutation \(Q\) of \((1, 2, \ldots, W)\):

• First, determine if grid A and grid B match for the current \((P, Q)\).
• If they do, find the minimum number of operations to reach that \((P, Q)\) from the initial state.

Then, we can find the minimum among the minimum numbers above. Here, if no pair \((P, Q)\) makes grid A identical to grid B, then it is impossible to make grid A equal grid B, so print -1.

The minimum number of operations required to reach the current \((P, Q)\) from the initial state is the sum of

• the minimum number of operations required to obtain the permutation \(P\) from initial sequence \((1, 2, \ldots, H)\) by repeatedly swapping adjacent element, and
• the minimum number of operations required to obtain the permutation \(Q\) from initial sequence \((1, 2, \ldots, W)\) by repeatedly swapping adjacent element;

in general, the number of operations required to obtain a desired sequence \(A = (A_1, A_2, \ldots, A_N)\) starting from the sequence \((1, 2, \ldots, N)\) by repeatedly swapping adjacent two elements is given as the inversion number of the permutation \(A\), i.e.

the number of pairs \((i, J)\) such that \(1 \leq i \lt j \leq N\) and \(A_i \gt A_j\).

Therefore, the number of operations required to reach the state \((P, Q)\) from the initial state can be obtained as the sum of the inversion number of \(P\) and the inversion number of \(Q\).

Alternatively, one can perform a Breadth-First Search (BFS) on the state of grid A itself (the arrangement of the \(HW\) integers) to get the correct answer to this problem.

We introduce sample code for this problem in C++ language (in the solution using exhaustive search of permutations).

#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1000000000;

int main(void)
{
  int h, w, a[6][6], b[6][6];
  cin >> h >> w;
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) cin >> a[i][j];
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) cin >> b[i][j];
  
  int p[6], q[6];
  for(int i = 1; i <= h; i++) p[i] = i;
  for(int i = 1; i <= w; i++) q[i] = i;
  
  int ans = inf;
  do{
    do{
      
      bool match = true;
      for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++){
        if(a[p[i]][q[j]] != b[i][j]) match = false;
      }
      if(!match) continue;
      
      int pinv = 0, qinv = 0;
      for(int i = 1; i <= h; i++) for(int j = 1; j <= h; j++) if(i < j && p[i] > p[j]) pinv++;
      for(int i = 1; i <= w; i++) for(int j = 1; j <= w; j++) if(i < j && q[i] > q[j]) qinv++;
      ans = min(ans, pinv+qinv);
      
    }while(next_permutation(q+1, q+w+1));
  }while(next_permutation(p+1, p+h+1));
  
  if(ans == inf) cout << -1 << endl;
  else cout << ans << endl;
  
  return 0;
}