Description

在 3X3 的棋盘上摆放着 8 个棋子，棋子的编号分别为 1 到 8，空格则用 0 表示。与空格直接相连的棋子可以移至空格中，这样原来棋子的位置就成为空格。现给出一种初始布局，求到达目标布局的最少步数。例如：

初始布局：

目标布局：

Format

Input

两个3×3的矩阵，0表示空格，第一个表示初始状态，第二个表示目标状态

Output

最少步数，如果无解就输出-1

Samples

2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5

5

Limitation

1s, 1024KiB for each test case.