{"raw_statement":[{"iden":"problem statement","content":"There is a grid with $H$ rows and $W$ columns. Initially, each integer from $1$ to $(H \\times W)$ is written exactly once in the grid.  \nSpecifically, for $1 \\leq i \\leq H$ and $1 \\leq j \\leq W$, the cell at the $i$\\-th row from the top and the $j$\\-th column from the left contains $S_{i,j}$.  \nBelow, let $(i,j)$ denote the cell at the $i$\\-th row from the top and the $j$\\-th column from the left.\nDetermine if it is possible to reach a state where, for all pairs of integers $(i,j)$ $(1 \\leq i \\leq H, 1 \\leq j \\leq W)$,  \nthe cell $(i,j)$ contains the integer $((i-1) \\times W + j)$ by repeating the following operation **at most $20$ times** (possibly zero).  \nIf it is possible, print the minimum number of operations required.  \nIf 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$.\n\n> Operation: Choose a rectangle of size $(H-1) \\times (W-1)$ from the grid and rotate it $180$ degrees.  \n> More precisely, choose integers $x$ and $y$ $(0 \\leq x, y \\leq 1)$,  \n> and for all pairs of integers $(i,j)$ satisfying $1 \\leq i \\leq H-1$ and $1 \\leq j \\leq W-1$,  \n> simultaneously replace the integer written in cell $(i+x,j+y)$ with the number written in cell $(H-i+x,W-j+y)$.\n\nNote 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."},{"iden":"constraints","content":"*   $3 \\leq H,W \\leq 8$\n*   $1 \\leq S_{i,j} \\leq H \\times W$\n*   If $(i,j) \\neq (i',j')$, then $S_{i,j} \\neq S_{i',j'}$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$H$ $W$\n$S_{1,1}$ $S_{1,2}$ $\\ldots$ $S_{1,W}$\n$S_{2,1}$ $S_{2,2}$ $\\ldots$ $S_{2,W}$\n$\\vdots$\n$S_{H,1}$ $S_{H,2}$ $\\ldots$ $S_{H,W}$"},{"iden":"sample input 1","content":"3 3\n9 4 3\n2 1 8\n7 6 5"},{"iden":"sample output 1","content":"2\n\nOperating in the following order will satisfy the conditions of the problem statement in $2$ operations.\n\n*   Operate by choosing the rectangle in the top-left corner. That is, by choosing $x=0$ and $y=0$.\n*   Operate by choosing the rectangle in the bottom-right corner. That is, by choosing $x=1$ and $y=1$.\n\nOn the other hand, it is impossible to satisfy the conditions with one or fewer operations, so print $2$.\n![image](https://img.atcoder.jp/abc336/75a97e79fc11bfe9406ef4e3bef74f37.png)"},{"iden":"sample input 2","content":"4 6\n15 18 1 14 3 4\n23 24 19 8 9 12\n13 2 17 6 5 16\n21 22 7 20 11 10"},{"iden":"sample output 2","content":"\\-1\n\nIt is impossible to satisfy the conditions with $20$ or fewer operations, so print $-1$."},{"iden":"sample input 3","content":"4 6\n1 4 13 16 15 18\n21 20 9 12 23 10\n17 14 5 6 3 2\n11 22 7 24 19 8"},{"iden":"sample output 3","content":"20"},{"iden":"sample input 4","content":"4 3\n1 2 3\n4 5 6\n7 8 9\n10 11 12"},{"iden":"sample output 4","content":"0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}