AT_past19_o 15パズル

$ 4\times 4 $ のマス目について、次をみたす状態を **良い盤面** と定義します。 > $ 1 $ 以上 $ 15 $ 以下の整数 $ i $ について $ i $ が書き込まれたマスがちょうど $ 1 $ つ存在する。 > それら以外に何かが書かれたマスは存在せず、すなわち何も書かれていないマスがただ $ 1 $ つ存在する。 相異なる良い盤面 $ S $ , $ T $ が与えられます。 ここで、良い盤面 $ S $ は $ 16 $ 個の整数 $ S_{i,j} $ $ (1\leq i,j\leq 4) $ によって与えられます。 $ 1\leq S_{i,j}\leq 15 $ のとき、 $ S $ の上から $ i $ 行目かつ左から $ j $ 列目のマスには $ S_{i,j} $ が書き込まれていることを、 $ S_{i,j}=-1 $ のとき、 $ S $ の上から $ i $ 行目かつ左から $ j $ 列目のマスには何も書き込まれていないことを表します。 $ T $ も同様に $ 16 $ 個の整数 $ T_{i,j} $ $ (1\leq i,j\leq 4) $ によって与えられます。 $ S $ から次の操作を繰り返して $ T $ の状態を作るために必要な最小の操作回数を出力してください。 ただし、 $ 30 $ 回以下の操作で $ T $ の状態を作る事ができないとき（何回繰り返しても作る事ができない場合を含む）は $ -1 $ を出力してください。 - 何も書き込まれていないマスと辺を共有するマスを $ 1 $ つ選び、そのマスに書き込まれている整数を何も書き込まれていないマスに書き込む。その後、選んだマスに書かれている整数を消す。

入力は以下の形式で標準入力から与えられる。 > $ S_{1,1} $ $ S_{1,2} $ $ S_{1,3} $ $ S_{1,4} $ $ S_{2,1} $ $ S_{2,2} $ $ S_{2,3} $ $ S_{2,4} $ $ S_{3,1} $ $ S_{3,2} $ $ S_{3,3} $ $ S_{3,4} $ $ S_{4,1} $ $ S_{4,2} $ $ S_{4,3} $ $ S_{4,4} $ $ T_{1,1} $ $ T_{1,2} $ $ T_{1,3} $ $ T_{1,4} $ $ T_{2,1} $ $ T_{2,2} $ $ T_{2,3} $ $ T_{2,4} $ $ T_{3,1} $ $ T_{3,2} $ $ T_{3,3} $ $ T_{3,4} $ $ T_{4,1} $ $ T_{4,2} $ $ T_{4,3} $ $ T_{4,4} $

$ S $ から問題文中の操作を繰り返して $ T $ の状態を作るために必要な操作回数を出力せよ。 ただし、 $ 30 $ 回以下の操作で $ T $ の状態を作る事ができないときは $ -1 $ を出力せよ。

### Sample Explanation 1 マス目の上から $ i $ 行目かつ $ j $ 列目のマスを $ (i,j) $ で表すことにします。 $ S $ における何も書かれていないマスは $ (4,4) $ です。 ここから次のようにして $ 3 $ 回の操作で $ T $ を作る事ができます。 - $ (3,4) $ を選ぶ。 $ (4,4) $ に $ 12 $ を書き込み、 $ (3,4) $ に書かれている整数を消す。 - $ (3,3) $ を選ぶ。 $ (3,4) $ に $ 11 $ を書き込み、 $ (3,3) $ に書かれている整数を消す。 - $ (2,3) $ を選ぶ。 $ (3,3) $ に $ 7 $ を書き込み、 $ (2,3) $ に書かれている整数を消す。 一方で、 $ 2 $ 回以下の操作で $ T $ を作ることはできないため、 $ 3 $ を出力します。  ### Sample Explanation 2 $ 30 $ 回以下の操作で $ T $ を作る事ができないため、 $ -1 $ を出力します。 ### Constraints - $ -1\leq S_{i,j},T_{i,j}\leq 15 $ - $ S_{i,j},T_{i,j}\neq 0 $ - $ S,T $ は相異なる良い盤面である。 - 入力はすべて整数