AT_abc332_d [ABC332D] Swapping Puzzle

[problemUrl]: https://atcoder.jp/contests/abc332/tasks/abc332_d $ H $ 行 $ W $ 列の $ 2 $ つのグリッド A, B が与えられます。 $ 1\ \leq\ i\ \leq\ H $ と $ 1\ \leq\ j\ \leq\ W $ を満たす各整数の組 $ (i,\ j) $ について、 $ i $ 行目 $ j $ 列目にあるマスをマス $ (i,\ j) $ と呼ぶとき、 グリッド A の マス $ (i,\ j) $ には整数 $ A_{i,\ j} $ が、 グリッド B の マス $ (i,\ j) $ には整数 $ B_{i,\ j} $ がそれぞれ書かれています。 あなたは「下記の $ 2 $ つのうちのどちらか $ 1 $ つを行う」という操作を好きな回数（ $ 0 $ 回でもよい）だけ繰り返します。 - $ 1\ \leq\ i\ \leq\ H-1 $ を満たす整数 $ i $ を選び、グリッド A の $ i $ 行目と $ (i+1) $ 行目を入れ替える。 - $ 1\ \leq\ i\ \leq\ W-1 $ を満たす整数 $ i $ を選び、グリッド A の $ i $ 列目と $ (i+1) $ 列目を入れ替える。 上記の操作の繰り返しによって、グリッド A をグリッド B に一致させることが可能かどうかを判定してください。 さらに、一致させることが可能な場合は、そのために行う操作回数の最小値を出力してください。 ここで、グリッド A とグリッド B が一致しているとは、 $ 1\ \leq\ i\ \leq\ H $ と $ 1\ \leq\ j\ \leq\ W $ を満たす全ての整数の組 $ (i,\ j) $ について、 グリッド A の マス $ (i,\ j) $ とグリッド B の マス $ (i,\ j) $ に書かれた整数が等しいこととします。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ A_{1,\ 1} $ $ A_{1,\ 2} $ $ \cdots $ $ A_{1,\ W} $ $ A_{2,\ 1} $ $ A_{2,\ 2} $ $ \cdots $ $ A_{2,\ W} $ $ \vdots $ $ A_{H,\ 1} $ $ A_{H,\ 2} $ $ \cdots $ $ A_{H,\ W} $ $ B_{1,\ 1} $ $ B_{1,\ 2} $ $ \cdots $ $ B_{1,\ W} $ $ B_{2,\ 1} $ $ B_{2,\ 2} $ $ \cdots $ $ B_{2,\ W} $ $ \vdots $ $ B_{H,\ 1} $ $ B_{H,\ 2} $ $ \cdots $ $ B_{H,\ W} $

グリッド A をグリッド B に一致させることが不可能な場合は `-1` を、 可能な場合はグリッド A をグリッド B に一致させるために行う操作回数の最小値を出力せよ。

### 制約 - 入力される値は全て整数 - $ 2\ \leq\ H,\ W\ \leq\ 5 $ - $ 1\ \leq\ A_{i,\ j},\ B_{i,\ j}\ \leq\ 10^9 $ ### Sample Explanation 1 初期状態のグリッド A の $ 4 $ 列目と $ 5 $ 列目を入れ替えると、グリッド A は下記の通りになります。 ``` 1 2 3 5 4 6 7 8 10 9 11 12 13 15 14 16 17 18 20 19 ``` 続けて、グリッド A の $ 2 $ 行目と $ 3 $ 行目を入れ替えると、グリッド A は下記の通りになります。 ``` 1 2 3 5 4 11 12 13 15 14 6 7 8 10 9 16 17 18 20 19 ``` 最後に、グリッド A の $ 2 $ 列目と $ 3 $ 列目を入れ替えると、グリッド A は下記の通りになり、グリッド B に一致します。 ``` 1 3 2 5 4 11 13 12 15 14 6 8 7 10 9 16 18 17 20 19 ``` 上に述べた $ 3 $ 回の操作でグリッド A をグリッド B に一致させることができ、 これより少ない回数の操作でグリッド A をグリッド B に一致させることはできないため、 $ 3 $ を出力します。 ### Sample Explanation 2 問題文中の操作をどのように行ってもグリッド A をグリッド B に一致させることは不可能であるため `-1` を出力します。 ### Sample Explanation 3 グリッド A ははじめからグリッド B に一致しています。